P1546 [USACO3.1] 最短网络 Agri-Net

点击查看代码

#include<bits/stdc++.h>
using namespace std;

// N为点数最大值，M为边数最大值(100个点最多约5000条边)
const int N=105, M=5050; 
int n, m; // m用来动态记录我们提取出的有效边数

struct Edge{
    int a,b,w;
    // 重载小于号，Kruskal按权值从小到大排序必备
    bool operator<(const Edge& W) const{
        return w<W.w;
    }
}edges[M];

int p[N];
long long res, cnt;

// 并查集核心：带路径压缩的寻根函数
int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

void kruskal(){
    sort(edges+1, edges+1+m); // 边排序

    for(int i=1; i<=n; i++) p[i]=i; // 并查集初始化

    for(int i=1; i<=m; i++){
        int a=find(edges[i].a), b=find(edges[i].b), w=edges[i].w;
        // 若祖先不同，说明加入此边不构成环，果断合并
        if(a!=b){
            p[a]=b;
            res+=w;
            // n个点只需要n-1条边，找齐即提前结束
            if(++cnt==n-1) break; 
        }
    }
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    
    cin>>n;
    m = 0; // 边数从0开始统计
    
    // 【核心思维转化】：双重循环读取邻接矩阵
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            int w;
            cin>>w;
            // 矩阵是对称的，只取右上角(i<j)即可避免重复建边，也避开了对角线的0
            if(i < j){
                edges[++m] = {i, j, w}; 
            }
        }
    }

    // 题目保证图一定连通，直接跑Kruskal然后输出结果即可
    kruskal();
    
    cout<<res<<"\n";

    return 0;
}