社区讨论

求助23pt

P1194买礼物参与者 1已保存回复 1

讨论操作

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

当前回复
1 条
当前快照
1 份
快照标识符
@lx4mpdu4
此快照首次捕获于
2024/06/07 19:54
2 年前
此快照最后确认于
2024/06/07 22:36
2 年前
查看原帖
CPP
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 505;
struct Node{
	int x, y, p;
}a[N];
int fa[N];
bool cmp(Node r, Node t){
	return r.p < t.p;
}
int find(int x){
	return fa[x] == x ? x : find(fa[x]); 
}
int main(){
	int n, cost, ans = 0;
	cin >> n >> cost;
	int cnt = 0;
	for(int i = 1; i <= n; i++)
		fa[i] = i;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			int t;
			cin >> t;
			if(i >= j || t == 0)
				continue;
			a[++cnt].x = i;
			a[cnt].y = j;
			a[cnt].p = t;
			//cout << "p test " <<a[cnt].x << " " << a[cnt].y << " " << a[cnt].p << "\n";	
		}
		a[++cnt].x = 0;//虚拟节点从0开始建 
		a[cnt].y = i;
		a[cnt].p = cost;
	}
	
	//cout << cnt << "\n"; 
	sort(a+1, a+cnt+1, cmp);
	int l = 0;
	for(int i = 1; i <= cnt && l <= n; i++){
		//cout << "test\n";
		int nx = find(a[i].x);
		int ny = find(a[i].y);
		if(nx != ny){
			l++;
			fa[nx] = ny;
			ans += a[i].p;
		}
	}
	cout << ans;
	return 0;
}

回复

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

正在加载回复...