【bzoj2654】tree

2015年1月16日3,1434

Description

  给你一个无向带权连通图,每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。
题目保证有解。

Input

  第一行V,E,need分别表示点数,边数和需要的白色边数。
接下来E行
每行s,t,c,col表示这边的端点(点从0开始标号),边权,颜色(0白色1黑色)。

Output

  一行表示所求生成树的边权和。

Sample Input

2 2 1
0 1 1 1
0 1 2 0

Sample Output

2

HINT

数据规模和约定
0:V<=10
1,2,3:V<=15
0,..,19:V<=50000,E<=100000
所有数据边权为[1,100]中的正整数。

题解

给白色边都加上一个值,做mst会使得选取的白边数量减少,所以可以二分它

 

  • ___2015年3月22日 下午11:53 回复

    弱弱的问一下 为什么边排序时为什么一定要白前黑后 黑白无序可以吗

    #1  
    • hzwer2015年3月23日 上午12:15 回复
      admin

      无序的话二分会出问题吧

      #11
      • ___2015年3月23日 上午12:25 回复

        是的 没排序会wa 求解释
        原来你还在线啊 orz

        #12
        • hzwer2015年3月23日 下午9:02 回复
          admin

          我要计算当前至多能取多少白边,当然要把白边放前面。由于保证有解,在cnt>=need且cnt取最小值的方案下,一定能有黑边把多余的白边代替掉
          我的做法也许比较奇怪?
          你看zky是这样做的:考虑把白色边权加上一个值x,那么最小生成树中的白色边数量的可行最大值g(x)与可行最小值f(x)随x增大而减小,然后就可以二分一个x使得need∈[f(x),g(x)]

          #13