每日一水第42弹(09 final E)

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=77398#problem/E

题意:给若干条边增加边权后使得所有路径的总权值一样,随便输出一种方案,要求总权值最小。

注意:每条路径上只能有一条边被增加

虽然看错题了,但还是ac了。

我看成加的边的总权值和最小了。

仔细观察一下, 假如一条边需要增加边权,那么这条边会有怎样的性质呢?

显然(233), 这条边的两端的点各自到S T都只有一种权值的路径。

那么是不是其他性质的边都不用去管了呢?

是的,要是一条边的两个点到各自的S T都有权值不相同的路径,那么就无解,一边有,一边没有,这条边权值加了也没用。

然后这其实就是一个最小割了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注