重铸华农荣光 我辈义不容辞

The eighteenth day - Kruskal

一下学这么多图论算法，感觉要爆炸了，得让时间来digest,学完算法基础课再回过来总结一次

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100010,M=200010,INF=0x3f3f3f3f;
int n,m;
int p[N];

struct Edge{
    int a,b,w;
    bool operator<(const Edge &W)const
    {
        return w<W.w;
    }
}edges[M];

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

int Kruskal()
{
    sort(edges,edges+m);
    for(int i=1;i<=n;i++) p[i]=i;

    int ans=0,cnt=0;
    for(int i=0;i<m;i++)
    {
        int a=edges[i].a,b=edges[i].b,w=edges[i].w;
        a=find(a),b=find(b);
        if(a!=b)
        {
            p[a]=b;
            ans+=w;
            cnt++;
        }
    }
    if(cnt<n-1) return INF;
    return ans;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b,w;
        cin>>a>>b>>w;
        edges[i]={a,b,w};
    }

    int ans=Kruskal();

    if(ans==INF) cout<<"impossible";
    else cout<<ans;

    return 0;
}