【BZOJ3876】【AHOI2014】支线剧情

给你一张图,可以不断从\(1\)号点出发走到任意一个点结束,每条边至少走一次,求走过的边权和的最小值。

直接建费用流,每条边设\(1\)的下限。

然后发现不记得带下界的网络流怎么做了。。

对于每条边,可以假设它已经先跑过了下界的流量,将这部分流量计算答案并将上界减去下界。

此时会有一个问题就是流量不平衡了。

对于一条边\(u->v\),我们可以假设下界流量在\(u\)处流入了一个黑箱,又在\(v\)处流回\(v\)。

故可以令这个黑箱接收流入流量的部分为\(T’\),回流流量的部分为\(S’\),每次从\(S’\)向\(v\)连边,从\(u\)到\(T’\)连边。此外再从原来的\(T\)向\(S\)连一条无穷大的边,新的网络流只要满流即说明有合法解。

如果要求原网络的最小费用流:直接对新图跑费用流即可。

如果要求原网络的最大流:记录当前可行流(就是\(T\)到\(S\)边中的流量),删除\(T\)到\(S\)的边,再从\(S\)到\(T\)跑一遍最大流,两者加起来就是原网络的最大流。

如果要求原网络的最小流:先不加\(T\)到\(S\)的边跑一遍,加上再跑一边,此时\(T\)到\(S\)边的流量为答案。我不知道怎么证= =

说点什么

您将是第一位评论人!

提醒
wpDiscuz