BZOJ 2095 [Poi2010]Bridges

发布于 2017-10-10  174 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2095

题意:显然的二分答案,然后求混合图欧拉回路....


实在没想好怎么说这个题意.. 题意即题解:

网络流求混合图欧拉回路流程:

1. 为原图的每条无向边任意定向

2. 这样我们转换原图为一个有向图,若存在节点出入度奇偶性不同,则无解。

3. 令点权为\(x_i=abs(degin_i-degout_i)/2\),出度大于入度和入度大于出度的节点分别与源汇点连边权为点权的边。原图定向前的无向边均连定向后的方向,边权为 1 的边。

4. 若满流,则有解。

 


一个非常弱的准退役OIER