[BZOJ2654] tree (kruskal & 二分答案)

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

HINT

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

Source

Solution

　　如果给所有白色边加上一个权值，所形成的最小生成树的白边数会随该权值的增大而减小，满足单调性，可以二分权值。

　　排序有一个技巧：我们每次考虑最多可以使用多少条白边，所以排序时若权值相同，白边排前黑边排后。如果排序不管黑边白边，那么所求的白边数会小于期望的答案，可能会导致WA。

　　当然黑边在前白边在后也行，题是死的人是活的。

 #include <bits/stdc++.h>

 using namespace std;

 struct edge

 {

     int u, v, w, col;

     bool operator < (const edge &rhs) const

     {

         return w == rhs.w ? col < rhs.col : w < rhs.w;

     }

 }e[];

 int n, m, fa[], ans;

 int getfa(int x)

 {

     return fa[x] = x == fa[x] ? x : getfa(fa[x]);

 }

 int Kruskal(int x)

 {

     int ecnt = , wcnt = , u, v;

     ans = ;

     for(int i = ; i <= n; i++)

         fa[i] = i;

     for(int i = ; i <= m; i++)

         if(!e[i].col) e[i].w += x;

     sort(e + , e + m + );

     for(int i = ; i <= m; i++)

     {

         u = getfa(e[i].u), v = getfa(e[i].v);

         if(u != v)

         {

             fa[v] = u, ans += e[i].w;

             if(!e[i].col) wcnt++;

             if(++ecnt >= n) break;

         }

     }

     for(int i = ; i <= m; i++)

         if(!e[i].col) e[i].w -= x;

     return wcnt;

 }

 int main()

 {

     int k, l = -, r = , mid;

     cin >> n >> m >> k;

     for(int i = ; i <= m; i++)

         cin >> e[i].u >> e[i].v >> e[i].w >> e[i].col;

     for(int i = ; i <= m; i++)

         e[i].u++, e[i].v++;

     while(l < r - )

     {

         mid = (l + r) / ;

         if(Kruskal(mid) < k) r = mid;

         else l = mid;

     }

     Kruskal(l);

     cout << ans - l * k << endl;

     return ;

 }

巴特西