ABC445G Knight Placement 题解
题外话场上由于不会二分图最大独立集痛失 AK，qwq。
Solution
首先尝试图论建模，如果两个空格子可以互相攻击就连一条无向边。此时问题转化成图上最大独立集。
对于一般图，最大独立集是 NP-Hard 的，但对于二分图有多项式时间算法。玩玩样例，大胆猜测图是二分图。
下面证明该性质。显然 \(a,b\) 可以都先除以 \(\gcd(a,b)\)。此时如果 \(a+b\) 是奇数则按照 \(i+j\) 的奇偶性给格子染色。否则 \(a,b\) 均为奇数，按照 \(i\) 的奇偶性染色即可。
然后跑出二分图最大独立集并输出方案即可。关于二分图最大独立集的求法，需要多步转化：
[*]二分图最大独立集 \(\to\) 最小顶点覆盖的补集。
[*]加入源汇点 \(s,t\)。\(s\) 向左部点连权为 \(1\) 的有向边，左部点向右部点连权为 \(+\infty\) 的边，右部点向 \(t\) 连权为 \(1\) 的边。则最小顶点覆盖转化成最小割。
[*]应用最大流最小割定理，转化成最大流。
对于输出方案，一个点在最大独立集中当且仅当连接它和 \(s/t\) 的边不在最小割中。
Code
直接手写了 ISAP。
#include #define rep(i,a,b) for(int i(a);i 分享、互助 让互联网精神温暖你我 感谢分享，下载保存了，貌似很强大 分享、互助 让互联网精神温暖你我 感谢分享
页:
[1]