bzoj 2654 tree – 二分法 – 最小生成树

<!–
h3 {
clear: both;
border-left: 5px solid rgb(0, 128, 255);
padding-left: 5px;
}
–>

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

Input

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

Output

一行表示所求生成树的边权和。V<=50000,E<=100000,所有数据边权为[1,100]中的正整数。

Sample Input

2 2 1
0 1 1 1
0 1 2 0

Sample Output

2

Hint

原数据出错，现已更新 by liutian,但未重测—2016.6.24

　　显然是MST，但是在Kruskal的过程中我们无法控制白边的数量。如果考虑修改边值，可以发现如果给白边的边权都加上一个delta，那么白边的数量随着delta的增大而减小。所以可以二分它去控制白边的数量。

Code

 /**
  * bzoj
  * Problem#2654
  * Accepted
  * Time:1892ms
  * Memory:3052k
  */
 #include<iostream>
 #include<cstdio>
 #include<ctime>
 #include<cctype>
 #include<cstring>
 #include<cstdlib>
 #include<fstream>
 #include<sstream>
 #include<algorithm>
 #include<map>
 #include<set>
 #include<stack>
 #include<queue>
 #include<vector>
 #include<stack>
 #ifndef WIN32
 #define Auto "%lld"
 #else
 #define Auto "%I64d"
 #endif
 using namespace std;
 typedef bool boolean;
 const signed int inf = (signed)((1u << ) - );
 #define smin(a, b) a = min(a, b)
 #define smax(a, b) a = max(a, b)
 #define max3(a, b, c) max(a, max(b, c))
 #define min3(a, b, c) min(a, min(b, c))
 template<typename T>
 inline boolean readInteger(T& u){
     char x;
     int aFlag = ;
     while(!isdigit((x = getchar())) && x != '-' && x != -);
     if(x == -) {
         ungetc(x, stdin);
         return false;
     }
     if(x == '-'){
         x = getchar();
         aFlag = -;
     }
     for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');
     ungetc(x, stdin);
     u *= aFlag;
     return true;
 } typedef class union_found{
     public:
         int *f;
         union_found():f(NULL) {}
         union_found(int points) {
             f = new int[(const int)(points + )];
             clear(points);
         }
         int find(int x) {
             if(f[x] != x)    return f[x] = find(f[x]);
             return f[x];
         }
         void unit(int fa, int so) {
             int ffa = find(fa);
             int fso = find(so);
             f[fso] = ffa;
         }
         boolean connected(int a, int b) {
             return find(a) == find(b);
         }
         void clear(int points) {
             for(int i = ; i <= points; i++)
                 f[i] = i;
         }
 }union_found; int delta = ; typedef class Edge {
     public:
         int from;
         int end;
         int val;
         boolean col;         inline int getVal() const {
             if(col)    return val + delta;
             return val;
         }
 }Edge; boolean operator < (const Edge& a, const Edge& b) {
     return a.getVal() < b.getVal();
 } int n, m, lim;
 union_found uf;
 Edge* edge; inline void init() {
     readInteger(n);
     readInteger(m);
     readInteger(lim);
     uf = union_found(n);
     edge = new Edge[(const int)(m + )];
     for(int i = ; i < m; i++) {
         readInteger(edge[i].from);
         readInteger(edge[i].end);
         readInteger(edge[i].val);
         readInteger(edge[i].col);
         edge[i].col ^= ;
     }
 } int res = ;
 int kruskal(int mid) {
     delta = mid;
     res = ;
     uf.clear(n);
     sort(edge, edge + m);
     int fw = , fin = ;
     for(int i = ; i < m; i++) {
         if(!uf.connected(edge[i].from, edge[i].end)) {
             uf.unit(edge[i].from, edge[i].end);
             fw += edge[i].col, fin ++, res += edge[i].val;
         }
     }
     return fw;
 } inline void solve() {
     int l = -, r = , c;
     while(l <= r) {
         int mid = (l + r) >> ;
         if((c = kruskal(mid)) < lim)    r = mid - ;
         else if(c > lim)    l = mid + ;
         else break;
     }
     printf("%d\n", res);
 } int main() {
     init();
     solve();
     return ;
 }