déce. 20 最短网络

https://www.luogu.com.cn/problem/P1546

一遍过

#include<bits/stdc++.h>
using namespace std;
#define in Read()
typedef long long ll;

int in{
    int i=0,f=1; char ch=0;
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') f=-1, ch=getchar();
    while('0'<=ch&&ch<='9') i=(i<<1)+(i<<3)+ch-48, ch=getchar();
    return i*f;
}

const int N=200;
int n,G[N][N];
struct edge{
    int u,v,w;
    edge(){};
    edge(int U,int V,int W){u=U,v=V,w=W;}
}e[N*N];
int fa[N],cnt,ans,tot;

bool cmp(const edge &a, const edge &b){return a.w<b.w;}
int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}

int main(){

    // freopen("1.in","r",stdin);

    n=in;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j){
            int w=in;
            if((!w)||i>j) continue;
            ++cnt;
            e[cnt]=edge(i,j,w);
        }

    sort(e+1,e+cnt+1,cmp);
    for(int i=1;i<=n;++i) fa[i]=i;

    for(int i=1;i<=cnt;++i){
        int u=get(e[i].u), v=get(e[i].v);
        if(u==v) continue;
        fa[u]=v;
        ans+=e[i].w;
        ++tot;
        if(tot==n-1) break;
    }

    printf("%d\n",ans);
    // for(int i=1;i<=cnt;++i) printf("%d %d %d\n",e[i].u,e[i].v,e[i].w);
    return 0;
    
}