题解：AT_agc017_e [AGC017E] Jigsaw

· · 题解

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

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

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

  1. LFRF 型，即积木左右两端都着地。

  2. LERE 型，即积木左右两端都不着地。

  3. LERF 型，即积木左端不着地，右端着地。

  4. LFRE 型，即积木左端着地，右端不着地。

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

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

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

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

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

考虑用类似 2-SAT 的方式构造。方法为，对于第 i 块积木，抽象成边 u \rightarrow v，如果：

这样有什么好处呢？

  1. 不会让两个效果不相同的状态碰撞。

  2. 可以使 x（1 \leq x \leq H）能且只能和 x 匹配（左右两边加 H 和不加是反的）。

  3. 拼接操作被转化为找到路径经过边。

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

考虑以下几个限制。

  1. 路径起点，即积木最左端编号 x 应当满足 x \leq H。

  2. 路径终点，即积木最右端编号 x 应当满足 x \geq H。

  3. 一条路径端点出度和入度不能相等。

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

#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;
}