bzoj 3158: 千钧一发 最小割

看到这道题 是没什么思路的。查了一句话题解说是最小割。让我想到了魔术球那题。想找二分图的性质,然而失败了。真是可惜。后来查了题解恍然大悟。

两个偶数显然满足gcd>1的条件。

两个奇数 (2a+1)^2 + (2b+1)^2 = 4a^2 + 4a + ab^2 + 4b + 2 = 2(2a^2 + 2b^2 + 2a + 2b + 1)我们发现括号内显然是一个奇数,没法提出一个2与先前提出的二配对,所以必然满足另外一个性质。

这样子我们发现矛盾必定发生在奇数偶数之间。

我们s->奇数

偶数->t

流量为b。

矛盾的点之间连inf即可。

发表评论