社区讨论

样例过了,但10个点RE

P2330[SCOI2005] 繁忙的都市参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mi7ctoj1
此快照首次捕获于
2025/11/20 19:34
4 个月前
此快照最后确认于
2025/11/20 19:34
4 个月前
查看原帖
dalao帮忙看下
C
//Kruskal
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

struct node{
	int s, e, w;
}edge[50000];
int f[310];
int n, m, maxx, k;

bool cmp(node a, node b) {
	return a.w <= b.w;
}

void init() {
	for(int i = 1; i <= n; i++) {
		f[i] = i;
	}
}

int find(int x) {
	if(f[x] != x) {
		f[x] = find(f[x]);
	}
	return f[x];
}

void Kruskal() {
	for(int i = 1; i <= m; i++) {
		int tx = find(edge[i].s);
		int ty = find(edge[i].e);
		if(tx != ty) {
			f[ty] = tx;
			k++;
			maxx = edge[i].w;
		}
		if(k == n - 1) {
			break;
		}
	}
}

int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> edge[i].s >> edge[i].e >> edge[i].w;
	}
	init();
	sort(edge + 1, edge + m + 1, cmp);
	Kruskal();
	cout << n - 1 << " " << maxx;
	return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...