P4258 [WC2016]挑战NPC 题解

· · 题解

解题思路

先声明一下：此题不是 NPC。毕竟出题人还不至于能在多项式时间复杂度内爆切 NPC 问题。

一种不正确的最初想法：把每个筐拆成 3 个点 u_i,u_i+m,u_i+2 \times m，所有 v_i 向 u_i 拆后的三个点连边，跑二分图的最大匹配。

hack:
Input:
1
2 2 3
1 1
2 1
2 2
Output:
2
1 2

在这里可能会因为边的遍历顺序问题而先跑边 (2,1) 而导致答案变成 1。

那么接着就是这道题奇特的建图方式了。不妨在上述的建图方式为基础的情况下把所有的 u,u+m,u+2 \times m 两两之间连边，然后跑一般图的最大匹配（改为一般图的原因：前面三个点的两两连边会形成奇环），最后答案就是最大匹配数 -n。

来证明一下这个结论。

对所有的 u_i,u_i+m,u_i+2\times m 分 4 种情况讨论：

  1. 其中有 0 个匹配点。

    本来的贡献应该是 1。内部点必然恰好有一组匹配。减去匹配在这种情况下即等于减去 0，所以贡献还是 1。

  2. 有 1 个。

    本来的贡献应该是 1。会发现内部必然有一组匹配，和那一个匹配点所处的匹配一加，贡献为 2。所以多出来 1，刚好是减去匹配点个数。

  3. 有 2 个。

    本来的贡献应该是 0。注意到三个点不可能再出现内部匹配的情况了，所以刚好减去匹配点个数。

  4. 有 3 个。

    和 2 个的情况同理。

所以对于任意一组“每个球都放在一个框中”的匹配，拿匹配数 -n 一定等于答案。为了使答案最大，当然是取最大匹配了。且求最大匹配时我们优先对球进行增广，然后再对框子所表示的点进行增广。这样便可保证“每个球都放在一个框中”。

代码

给个这道题的重点部分（建图的部分）：

//输入+建边
scanf("%d%d%d", &n, &m, &e);
for(int i = 1; i <= m; i++){
    Add(i + n, i + m + n), Add(i + m + n, i + n);
   Add(i + n, i + 2 * m + n), Add(i + 2 * m + n, i + n);
   Add(i + m + n, i + 2 * m + n), Add(i + 2 * m + n, i + m + n);
}
for(int i = 1; i <= e; i++){
    int v, u; scanf("%d%d", &v, &u);
    Add(v, u + n)， Add(v, u + m + n), Add(v, u + 2 * m + n);
    Add(u + n, v), Add(u + m + n, v), Add(u + 2 * m + n, v);
}

//之后跑一般图的最大匹配