题目 Bob was in trouble.He rubbed the magic ring on his finger, and you came out of the ground.
You are given an undirected graph G which contains n vertices labelled from 1 to n, with m weighted edges between them coloured in black or white.You have to choose some edges in G such that there is at least one path between any two vertices only passing by selected edges, and you can select no more than k white edges.There may be multiple available strategies to determine these edges, and you are asked to find out the way with a maximum total weight of edges.
Input The first line contains an integer T (1≤T≤5) indicating the number of test cases.
For each test case, the first line contains three integers n (1≤n≤50000),m and k (1≤k≤m≤500000).
Each of the following m lines contains four integers u,v (1≤u,v≤n),w (0≤w≤100000) and c (0≤c≤1) describing an edge of weight w and colour c between the u-th vertex and the v-th vertex. Here an edge is white if c=1, or black if c=0.
Note that there may be multiple edges between some vertices, and self-loops are also allowed.
Output For each test case, output a single line with an integer indicating the maximum total weight of selected edges, or output -1 if there is no solution for the given graph.
Sample Input 1 5 6 2 1 2 0 0 1 3 5 1 1 5 1 0 2 3 6 1 2 4 2 0 3 4 7 1 Sample Output 16
题意 给n个结点编号1~n，给m个有边权的边，边又分为白边与黑边，标记出其中若干个边，其中白边最多只能标记k条，令其中任何两个点都有一条路径只经过被标记的边，输出被标记的边权和，如果有多解，输出其中边权和最大的一种情况。
思路 因为黑边可以任意选，先选出所有黑边，并把其中黑边所连接的点标记出来，然后按边权从大到小遍历全部白边，如果能够选出k条白边令整个图联通就有解，反之无解。 PS.思路很简单，但是我码代码的能力实在太弱，本来一道水题代码写的又臭又长，好在一发a了，不然改代码能让我痛苦死………… 代码
#include<bits/stdc++.h> using namespace std; #define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define ll long long const int MAXN = 5e4 + 5, MAXM = 5e5 + 5; int t, n, m, k; struct node { int u, v, w; }white[MAXM], black[MAXM]; int wnum, bnum; int vis[MAXN], jud[MAXN], cnt[MAXN]; bool cmp(node a, node b) { return a.w > b.w; } int main(void){ IO; cin >> t; while(t--) { memset(vis,0,sizeof(vis)); memset(jud,0,sizeof(jud)); memset(cnt,0,sizeof(cnt)); memset(white,0,sizeof(white)); memset(black,0,sizeof(black)); wnum = 0, bnum = 0; cin >> n >> m >> k; for(int i = 0; i < m; i++) { int c;node x;cin >> x.u >> x.v >> x.w >> c; if(c)white[++wnum] = x; else black[++bnum] = x; } jud[1] = 1;int num = 0, now = 1; ll ans = 0; for(int i = 1; i <= bnum; i++) { if(!vis[black[i].u])vis[black[i].u] = 1,num++; if(!vis[black[i].v])vis[black[i].v] = 1,num++; ans += black[i].w; } sort(white + 1, white + wnum + 1, &cmp); queue<int> q; for(int i = 1; i <= wnum; i++) { if(!vis[white[i].u] && !vis[white[i].v]) { ans += white[i].w; k--; now++; vis[white[i].u] = now; vis[white[i].v] = now; cnt[now] += 2; }else if(!vis[white[i].u]) { ans += white[i].w; k--; vis[white[i].u] = vis[white[i].v]; cnt[vis[white[i].v]]++; if(jud[vis[white[i].v]])num++; }else if(!vis[white[i].v]) { ans += white[i].w; k--; vis[white[i].v] = vis[white[i].u]; cnt[vis[white[i].u]]++; if(jud[vis[white[i].u]])num++; }else if(vis[white[i].u] == vis[white[i].v]) { q.push(white[i].w); }else if(vis[white[i].u] != vis[white[i].v]) { if(jud[vis[white[i].u]] && jud[vis[white[i].v]]) { q.push(white[i].w); }else if(jud[vis[white[i].u]] || jud[vis[white[i].v]]) { ans += white[i].w; k--; if(jud[vis[white[i].u]])num += jud[vis[white[i].v]]; else num += jud[vis[white[i].u]]; jud[vis[white[i].u]] = jud[vis[white[i].v]] = 1; }else { int mi = min(vis[white[i].u], vis[white[i].v]), ma = max(vis[white[i].u], vis[white[i].v]); for(int i = 1; i <= n; i++) { if(vis[i] == mi)vis[i] == ma; } cnt[ma] += cnt[mi]; cnt[mi] = 0; } } if(num == n) { if(k <= 0)break; while(!q.empty()) { ans += q.front(); q.pop(); k--; if(k == 0)break; } for(int j = i + 1; j <= wnum && k > 0; j++) { ans += white[j].w; k--; } break; } } if(num == n) { if(k >= 0) { cout << ans << '\n'; }else { cout << -1 << '\n'; } }else { cout << -1 << '\n'; } } }