繁忙的都市(kruskal)

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=310,M=10000;
int p[N],n,m;
int find(int x){
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
struct node{
    int a,b,dist;
    bool operator<(const node&a)const{
        return dist<a.dist;
    }
}edges[M];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    p[i]=i;
    for(int i=0;i<m;i++)
    cin>>edges[i].a>>edges[i].b>>edges[i].dist;
    sort(edges,edges+m);
    int res=0;
    for(int i=0;i<m;i++){
        int a=find(edges[i].a),b=find(edges[i].b),c=edges[i].dist;
        if(a!=b){
            p[a]=b;
            res=c;
        }
    }
    cout<<n-1<<" "<<res<<endl;
    return 0;
}

 

上一篇:2019牛客多校第四场J free——分层图&&最短路


下一篇:POJ-3281-Dining(网络流, 拆点)