原题面:
http://codeforces.com/gym/101667/attachments
[题意]
给你n个边,定义一个函数F(e) 。F(e)等于删除多少条边后,这条边能加入最小生成树,求所有边的F(e)的总和。
[题解]
这道题学长在现场切了,但是我还是想要写一下这个题的题解来回顾一下。
首先,一条边要成为MST上的一条,必然要是唯一使端点联通的最小边。
所以针对这题,我们需要每次把比该边短的边都连在图内,对端点进行最大流,就能知道最少删几条边,这两个点不连通,即F(e)