社区讨论

求挑错

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 条回复,欢迎继续交流。

正在加载回复...