R24024536 记录详情

#include<iostream>
#include<algorithm>
using namespace std;

struct Line {
	int u, v, w;
}; 

const int MAXM = 100000 + 5;

Line line[MAXM], ans[MAXM];
int f[MAXM];
int n, m, k;
int tot = 0;

bool cmp(Line a, Line b) {
	return a.w > b.w;
}

bool cmp1(Line a, Line b) {
	return a.w < b.w;
}

int find(int k) {
	return k == f[k] ? k : f[k] = find(f[k]);
}

void connect(int u, int v) {
	f[find(u)] = find(v);
}

bool query(int u, int v) {
	return find(u) == find(v);
}

int main() {
	cin >> n >> m >> k;
	for(int i = 0; i < m; i++) {
		cin >> line[i].u >> line[i].v >> line[i].w;
	}
	
	sort(line, line + m, cmp);
	
	for(int i = 1; i <= n; i++) {
		f[i] = i;
	}
	
	int cnt = 0;
	for(int i = 0; i < m; i++) {
		if(!query(line[i].u, line[i].v)) {
			connect(line[i].u, line[i].v);
			tot++;
			if(line[i].w == 0) {
				line[i].w = -1;
				cnt++;
			}
			if(tot == n - 1) {
				break;
			}
		}
	}
	
	if(cnt > k || tot < n - 1) {
		cout << "no solution" << endl;
		return 0;
	}
	cnt = 0;
	tot = 0;
	
	sort(line, line + m, cmp1);
	
	for(int i = 1; i <= n; i++) {
		f[i] = i;
	}
	
	for(int i = 0; i < m; i++) {
		if(!query(line[i].u, line[i].v)) {
			if(line[i].w == 1 || cnt < k) {
				connect(line[i].u, line[i].v);
				ans[tot++] = line[i]; 
				
				if(line[i].w < 1) {
					line[i].w = 0;
					cnt++;
				}
			}
		}
	}
	
	if(tot < k) {
		cout << "no solution" << endl;
		return 0;
	}
	
	for(int i = 0; i < tot; i++) {
		if(ans[i].w == -1) {
			ans[i].w = 0;
		}
		cout << ans[i].u << " " << ans[i].v << " " << ans[i].w << endl;
	}
	
	return 0;
} 

第一个测试点WA