【网络流】MOS-Bridges

WeLikeStudying · 2022-09-14 14:22:05 · 题解

• 本来以为转化为欧拉回路之后会有不错的接近线性的做法的，没想到最后居然是网络流。
• 欲哭无泪，所以是不是可以用网络流求解无向图欧拉回路。

题意

• 给定一个图，边有权值且正着走和逆着走有不同权值，在这个图上求一条最大边权最小的欧拉回路，从点 1 出发，要求输出方案。

分析

• 考虑二分答案，就变成了欧拉回路问题，不过有的边是有向边，有的边是无向边，很快你就会发现，针对单独的有向图和无向图的算法在这里都无法派上用场。
• 我们尝试枚举每条无向边的方向判断是否可以是欧拉回路，你发现有向图存在欧拉回路的判定居然十分简洁：忽略边方向连通（完全可以一开始判定），入度与出度相等（这太数值化了）。
• 经过一些奇妙的脑回路之后你容易想到一个网络流的判定方法：初始时先随机定向，将每个点的入度与出度之差设为点权（显然，点权首先必须都是偶数，因为定向不会改变奇偶性，这点可以先特判，容易发现，点权的意义是合法流流入和流出的流量差），正权点连超级源，容量为权值，负权点连超级汇，容量为权值相反数，然后每条无向边连向原方向的反方向，流量为 2，跑一遍最大流。
• 如果存在合法方案那么最大流一定把源点和汇点的直连边满流，同样，由于增广路等常见最大流算法的特性，每条边的流量都是偶数，故方案一定合法，代码。