给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有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
思路：二分+Dijkstra 假设对当前图求一边最小生成树，其中白色边有tot条，假设tot > need，那么我们给每一条白色边加上一个mid,再求一边最短路，那么tot肯定是要减少的；若tot < need，那么就可以给每个白色边减去一个mid；这样就具有单调性，只需要去二分找这个mid，每次做一下check就可以了。
code:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct node { int x,y,w,col; }map[100010]; struct node1 { int x,y,w,co; }a[100010]; int n,m,k,tot,tt,sum,ans; int f[100020]; bool cmp(node1 aa,node1 bb) { if(aa.w == bb.w) return aa.co < bb.co; return aa.w < bb.w; } int find(int x) { if(f[x] != x) f[x] = find(f[x]); return f[x]; } void dij(int mid) { for(int i=1;i<=n;i++) f[i] = i; tot = 0; sum = 0; for(int i=1;i<=m;i++) { a[i].x = map[i].x; a[i].y = map[i].y; a[i].w = map[i].w; if(!map[i].col) a[i].w += mid; a[i].co = map[i].col; } sort(a+1,a+1+m,cmp); for(int i=1;i<=m;i++) { int fx = find(a[i].x); int fy = find(a[i].y); if(fx != fy) { if(!a[i].co) tot++; f[fy] = fx; sum += a[i].w; } } } int main() { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;i++) { scanf("%d%d%d%d",&map[i].x,&map[i].y,&map[i].w,&map[i].col); map[i].x++;map[i].y++; if(!map[i].col) tt++; } int l =-110; int r =110; while(l<=r) { int mid = (l+r)/2; dij(mid); if(tot >= k) { ans = sum-k*mid; l = mid+1; } else r = mid-1; } printf("%d\n",ans); return 0; }