社区讨论
求助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 条回复,欢迎继续交流。
正在加载回复...