codevs 1231 最优布线问题

1. 题目链接

2. 最小生成树模板题。下面是用kruskal：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e5+7;
struct node{
    int u,v,w;
    friend bool operator<(node a,node b){return a.w<b.w;}
};
int fa[N],n,m;long long ans;vector<node>e;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void kruskal(){
    sort(e.begin(),e.end());
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=0;i<e.size();i++){
        int p=e[i].u,q=e[i].v;
        if(find(p)==find(q))continue;
        fa[find(p)]=find(q);
        ans+=e[i].w;
    }
    cout<<ans<<endl;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        node a;cin>>a.u>>a.v>>a.w;
        e.push_back(a);
    }
    kruskal();
}