当前位置: 代码迷 >> 综合 >> [CF gym]2017-2018 ACM-ICPC, Asia Daejeon Regional Contest E How Many to Be Happy?
  详细解决方案

[CF gym]2017-2018 ACM-ICPC, Asia Daejeon Regional Contest E How Many to Be Happy?

热度:71   发布时间:2023-12-13 04:47:48.0

原题面:

        http://codeforces.com/gym/101667/attachments

    




[题意]

        给你n个边,定义一个函数F(e) 。F(e)等于删除多少条边后,这条边能加入最小生成树,求所有边的F(e)的总和。




[题解]

        这道题学长在现场切了,但是我还是想要写一下这个题的题解来回顾一下。

        首先,一条边要成为MST上的一条,必然要是唯一使端点联通的最小边。

        所以针对这题,我们需要每次把比该边短的边都连在图内,对端点进行最大流,就能知道最少删几条边,这两个点不连通,即F(e)

  相关解决方案