BZOJ 2095 [Poi2010]Bridges


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

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


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

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

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

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

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

4. 若满流,则有解。

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 2095 [Poi2010]Bridges


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , ,