题解：AT_agc017_e [AGC017E] Jigsaw

以前觉得自己图论建模水平还不错（可能是秒了狼和羊的故事和 3rd Ucup Stage12 H），做到这道题，发现自己图论建模真的太菜了。

本题最显然也是唯一显然的一点是，两块积木拼起来能够使得下面没有空格，其中一块积木的对应一端肯定着地。

既然这样，我们试着把积木分类吧，我们开始分：

LFRF 型，即积木左右两端都着地。
LERE 型，即积木左右两端都不着地。
LERF 型，即积木左端不着地，右端着地。
LFRE 型，即积木左端着地，右端不着地。

这样分完之后，我们很容易就能看出，~~分成四类一点也不优雅~~这种分法太冗余了。怎么化简？

看看题，中间部分高度恒为

H

，既然题目说了是着地，仔细一想，我们把中间一块去掉，着地和不着地的状态不会发生变化。得出结论，出题人设置中间一列只是因为左右两列要有一个东西连起来。现在中间就不用考虑了。

然后进一步思考，左边和右边本身没什么联系，可以考虑把积木左右拆开来，一个左匹配一个右。

接下来就是最重要也是最神仙的一步。左右之间有联系，那就不把积木转成点。既然积木连接了一个左一个右，为什么不能抽象成一条边呢？

然后就是考虑如何把边连接的两个点建模出来。

考虑用类似 2-SAT 的方式构造。方法为，对于第

i

块积木，抽象成边

u \rightarrow v

，如果：

$C_i=0$ ， $u = A_i$ 。
$C_i \neq 0$ ， $u = C_i + H$ 。
$D_i = 0$ ， $v = B_i + H$ 。
$D_i \neq 0$ ， $v = D_i$ 。

这样有什么好处呢？

不会让两个效果不相同的状态碰撞。
可以使 $x$ （ $1 \leq x \leq H$ ）能且只能和 $x$ 匹配（左右两边加 $H$ 和不加是反的）。
拼接操作被转化为找到路径经过边。

最后就是考虑怎么找合法路径了。

考虑以下几个限制。

路径起点，即积木最左端编号 $x$ 应当满足 $x \leq H$ 。
路径终点，即积木最右端编号 $x$ 应当满足 $x \geq H$ 。
一条路径端点出度和入度不能相等。

有了这些限制，我们维护出入度，再写个并查集就好了。

CPP

#include<bits/stdc++.h>
using namespace std;
int n, h, fa[405], ind[405], oud[405], chk[405];
int find(int x){
	if (fa[x] == x)
		return x;
	else
		return fa[x] = find(fa[x]);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> h;
	for (int i = 1; i <= (h << 1); i++){
		fa[i] = i;
	}
	for (int i = 1; i <= n; i++){
		int a, b, c, d, u, v;
		cin >> a >> b >> c >> d;
		u = (c ? c + h : a);
		v = (d ? d : b + h);
		++oud[u];
		++ind[v];
		int fu = find(u), fv = find(v);
		if (fu != fv)
			fa[fu] = fv;
	}
	for (int i = 1; i <= h; i++){//不满足限制 1
		if (oud[i] < ind[i]){
			cout << "NO";
			exit(0);
		}
	}
	for (int i = h + 1; i <= (h << 1); i++){//不满足限制 2
		if (ind[i] < oud[i]){
			cout << "NO";
			exit(0);
		}
	}
	for (int i = 1; i <= (h << 1); i++){
		if ((ind[i] == oud[i] && ind[i] == 0) || (ind[i] != oud[i])){
			chk[find(i)] = 1;
		}
	}
	for (int i = 1; i <= (h << 1); i++){
		if (fa[i] == i && chk[i] == 0){//不满足限制 3
			cout << "NO";
			exit(0);
		}
	}
	cout << "YES";
	return 0;
}

题解：AT_agc017_e [AGC017E] Jigsaw

文章操作

相关推荐

评论

题解：AT_agc017_e [AGC017E] Jigsaw