题解 AT2668 【[AGC017E] Jigsaw】

· · 题解

在博客园食用更佳：https://www.cnblogs.com/PinkRabbit/p/AGC017.html。

注意到，如果 C_i \ne 0，则 A_i 毫无意义，同理如果 D_i \ne 0，则 B_i 也是毫无意义。

我们可以把每个拼图抽象成一个数对：(l_i, r_i)。需要满足：

对于两块拼图 (l_i, r_i) 和 (l_j, r_j)，想让 i 拼图能拼在 j 拼图的左边，当且仅当 r_i = l_j 的时候才成立。

把所有 l, r 看成图中的节点，对于每块拼图，我们可以从 l_i 向 r_i 连一条边。

则题目即是要求：把这张图分成若干条路径，每条边被恰好经过一次，且路径的起点和终点节点有特殊要求（要贴合桌沿）。

实际上就只有两类点，必须从左侧点出发到达右侧点（但是这张图不是二分图）。

要如何判断是否可行呢？我的想法是：反正已知需要花费的路径数目（通过度数确定），那么跑一下最大费用最大流就行。

这样好像确实是可行的，毕竟 H 才 200，而且图中都是单位边权单位费用，也许有些玄学性质保证复杂度。

不过题解给出了更优秀的判定方法：

  1. 首先要保证每个左侧点的出度不比入度少，右侧点入度不比出度少。

  2. 对于每个弱连通分量，其中左侧点中至少要有一个能作为起点的点：也就是出度比入度多。

只要满足这两个条件就一定可以给出方案了，不难证明是正确的（欧拉回路那套理论）。

#include <cstdio>
#include <vector>

const int MH = 405;

int N, H, deg[MH];
std::vector<int> G[MH];

int ok, vis[MH];
void DFS(int u) {
    vis[u] = 1;
    if (deg[u]) ok = 1;
    for (int v : G[u]) if (!vis[v]) DFS(v);
}

int main() {
    scanf("%d%d", &N, &H);
    for (int i = 1; i <= N; ++i) {
        int a, b, c, d, x, y;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        if (!c) x = a;
        else x = c + H;
        if (!d) y = b + H;
        else y = d;
        ++deg[x], --deg[y];
        G[x].push_back(y), G[y].push_back(x);
    }
    for (int i = 1; i <= H; ++i)
        if (deg[i] < 0 || deg[i + H] > 0) return puts("NO"), 0;
    for (int i = 1; i <= 2 * H; ++i) if (!G[i].empty() && !vis[i]) {
        ok = 0, DFS(i);
        if (!ok) return puts("NO"), 0;
    }
    puts("YES");
    return 0;
}