社区讨论
求挑错
P1546[USACO3.1] 最短网络 Agri-Net参与者 3已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mi7unvah
- 此快照首次捕获于
- 2025/11/21 03:54 4 个月前
- 此快照最后确认于
- 2025/11/21 03:54 4 个月前
CPP
#include <cstdio>
#include <algorithm>
using namespace std;
const int X = 100;
int M,N;
struct node{int nxt,start,dis;}e[(X^2)+10];
int fa[X+5],cnt=0;
long long ans = 0;
int k = 0;
int n,m;
bool cmp(node x,node y){return x.dis < y.dis;}
//void add(int from,int to,int dis)
//{
// e[++cnt].to = to;
// e[cnt].dis = dis;
// e[cnt].nxt = fa[from];
// fa[from] = cnt;
//}
int find(int x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);}
void kruskal()
{
for (int i = 1 ;i <= cnt ;i ++){
int x = find (e[i].start);
int y = find (e[i].nxt);
if(x == y) continue;
ans += e[i].dis;
fa[x] = y,k++;
if( k == N ) break;
}
}
int main()
{
scanf("%d",&N);
for (int i = 1 ;i <= N ;i++){
fa[i]= i;
}
for (int i = 1 ; i <= N ;i ++){
for(int j = 1 ;j <= N ; j ++){
scanf("%d",&n);
if(j > i){
e[++m] = (node){i,j,n};
}
}
}
sort(e+1,e+1+m,cmp);
kruskal();
printf("%lld",ans);
return 0;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...