最小生成树秒掉了!
原题链接：18537.我心中珍藏的游戏
2024-04-02 17:18:33
发布于：广东
11阅读
0回复
0点赞
#include <iostream>
#include <algorithm>
using namespace std;
struct node{
int x,y,num;
}a[640005];
int dad[805],size;
int Find(int x) {
if (dad[x]==x) return x;
return dad[x]=Find(dad[x]);
}
int cmp(node x,node y) {
return x.num>y.num;
}
int main() {
int n;
scanf("%d",&n);
for (int i=1;i<=n;i++) {
dad[i]=i;
for (int j=1;j<=n;j++) {
int num;
scanf("%d",&num);
if (i<j) {
a[++size].x=i;
a[size].y=j;
a[size].num=num;
}
}
}
long long sum=0;
sort(a+1,a+1+size,cmp);
for (int i=1;i<=size;i++) {
int u=Find(a[i].x);
int v=Find(a[i].y);
if (u!=v) {
sum+=a[i].num;
dad[u]=v;
}
}
printf("%lld",sum);
return 0;
}
这里空空如也
有帮助，赞一个