闲话 基于本题没有题解，那我来水一发网络流，先声明一下，本篇题解可能有部分口胡现象（本人太菜不会证明，但结论是对的，感性理解一下）。 正文 本题的结果不能直接用网络流跑出来（至少我不能）。网络流的题重在建图，但这题不一样，他更多是在考察对残余网络的操作。 首先我们看这个东西和二分图匹配有点像所以先把图拆点然后画出来，如下。 显然这个图的最大流（最大匹配）是 ，即最多能选出三...

闲话 基于本题已经有人写了匈牙利的题解，这里我就来写一篇关于网络流的题解。 能做这道题的人应该都能看出是裸的最小重复路径覆盖问题吧。 虽然最小路径覆盖原代码只会红一个点。 思路 首先网络流的难点一直都是在于建图，那么这道题该怎么建图呢？ 引入 先想一下普通的最小路径覆盖集问题，我们的见图方式是将每个点拆为出点和入点，目的是保证每个点刚好只被所有路径经过一次。 然后将源点和入点...