代码：
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<cmath> 5 #include<iostream> 6 #include<cctype> 7 8 using namespace std; 9 10 const int N = 50100; 11 12 struct Edge{ 13 int u,v,w,c; 14 bool operator < (const Edge &a) const { 15 if (w == a.w) return c < a.c; 16 return w < a.w; 17 } 18 }e[200100]; 19 int fa[N]; 20 int n,m,k,Ans = 0; 21 22 inline char nc() { 23 static char buf[100000],*p1 = buf,*p2 = buf; 24 return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; 25 } 26 inline int read() { 27 int x = 0,f = 1;char ch = nc(); 28 for (; !isdigit(ch); ch=nc()) if(ch=='-') f=-1; 29 for (; isdigit(ch); ch=nc()) x=x*10+ch-'0'; 30 return x * f; 31 } 32 int find(int x) { 33 if (x == fa[x]) return x; 34 return fa[x] = find(fa[x]); 35 } 36 bool check(int x) { 37 for (int i=1; i<=m; ++i) { 38 if (e[i].c == 0) e[i].w += x; 39 } 40 sort(e+1,e+m+1); 41 for (int i=1; i<=n; ++i) fa[i] = i; 42 int cnt = 0,cntwhite = 0,ans = 0; 43 for (int i=1; i<=m; ++i) { 44 int fu = find(e[i].u),fv = find(e[i].v); 45 if (fu == fv) continue; 46 fa[fv] = fu; 47 ans += e[i].w; 48 cnt ++; 49 if (e[i].c == 0) cntwhite ++; 50 if (cnt == n-1) break; 51 } 52 for (int i=1; i<=m; ++i) { 53 if (e[i].c == 0) e[i].w -= x; 54 } 55 if (cntwhite < k) return false; 56 ans -= x * k; 57 Ans = ans; 58 return true; 59 } 60 int main () { 61 n = read(),m = read(),k = read(); 62 for (int i=1; i<=m; ++i) { 63 e[i].u = read() + 1,e[i].v = read() + 1,e[i].w = read(),e[i].c = read(); 64 } 65 int L = -101,R = 101; 66 while (L <= R) { 67 int mid = (L + R) / 2; 68 if (check(mid)) L = mid + 1; 69 else R = mid - 1; 70 } 71 cout << Ans; 72 return 0; 73 }