【题解】最小路径覆盖 网络流24题

传送到洛谷
传送到LOJ

Solution

这题也用到了拆点的方法,将原图中的每个点拆成入点和出点,并增加\(S\)点和\(T\)点。然后按原图连有向边,容量为1,再从\(S\)到所有入点、所有出点到\(T\)分别连容量为1的有向边。最少路径数等于\(n\)减去网络最大流。

证明的话,大概可以这样想:假设一开始所有点都没有连边,那么所需要的路径数当然等于\(n\),流量每增加1,相当于原图中两个点用一条路径连起来了,那么所需要的路径数就会减少1;而由于所有与\(s\)或\(t\)连通的边容量均为1,正好符合“\(V\)中每个顶点恰好在\(P\)的一条路上”,所以这样做是正确的。
方案的话,把所有流量为1并且不与\(s\)或\(t\)连通的路径连起来就可以啦!我用的是链表,然而CE/RE了好久。。。我对于指针这一块还不是很熟练QAQ

Code

 

发表评论