Kruscal

TLE_ooo · 2019-06-15 14:56:00 · 个人记录

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int from,to,val;
}edge[10005];
bool cmp(node x,node y)
{
    return x.val<y.val;
}
int father[105];
int find(int x)
{
    if(father[x]!=x)
        father[x]=find(father[x]);
    return father[x];
}
void unionn(int x,int y)
{
    x=find(x);y=find(y);
    father[y]=x;
}
int main()
{
    int n,x,m=0;
    cin>>n;
    for(int i=1;i<=n;i++)
        father[i]=i;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            cin>>x;
            if(i<j)
            {
                m++;
                edge[m].from=i;
                edge[m].to=j;
                edge[m].val=x;
            }
        }
    sort(edge+1,edge+m+1,cmp);
    int cnt=0,sum=0;
    for(int i=1;i<=m;i++)
    {
        int x=edge[i].from;
        int y=edge[i].to;
        if(find(x)==find(y))
            continue;
        cnt++;
        sum+=edge[i].val;
        unionn(x,y);
        if(cnt==n-1)
            break;
    }
    cout<<sum;
    return 0;
}