BZOJ 3714: [PA2014]Kuglarz(最小生成树)

#include<cstdio>
#include<algorithm>
#define int long long 
const int MAXN=3*1e6+10;
using namespace std;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int N;
struct node
{
    int u,v,w;
}edge[MAXN];
int num=1;
void AddEdge(int x,int y,int z)
{
    edge[num].u=x;
    edge[num].v=y;
    edge[num++].w=z;
}
int comp(const node &a,const node &b){return a.w<b.w;}
int fa[MAXN];
int find(int x)
{
    if(fa[x]==x) return fa[x];
    else return fa[x]=find(fa[x]);
}
void unionn(int x,int y)
{
    int fx=find(x);
    int fy=find(y);
    fa[fx]=fy;
}
void Kruskal()
{
    sort(edge+1,edge+num,comp);    
    int tot=0,sum=0;
    for(int i=1;i<=num-1;i++)
    {
        if(find(edge[i].u)!=find(edge[i].v))
        {
            unionn(edge[i].u,edge[i].v);
            sum+=edge[i].w;
            tot++;
            if(tot==N) break;
        }
    }
    printf("%lld",sum);
}
main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    N=read();
    for(int i=1;i<=N;i++) fa[i]=i;
    for(int i=1;i<=N;i++)
    {
        for(int j=i;j<=N;j++)
        {
            int x=read();
            AddEdge(i-1,j,x);
        }
    }
    Kruskal();
    return 0;
}