P1550 [USACO08OCT] Watering Hole G

· · 题解

P1550 [USACO08OCT] Watering Hole G

题目思路：

与 P1194 买礼物 题思路一样，详情请看该题题解

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct edge{
    int u,v,w;
    bool operator<(const edge &a)const{return w<a.w;}
}e[N];
int fa[N];
int find(int x){
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
int main(){
    int w,n,m(0);
    cin>>n;
    for(int i=0;i<=n;i++){
        fa[i]=i;
    }
    for(int i=1;i<=n;i++){
        cin>>w;
        e[++m].u=0;
        e[m].v=i;
        e[m].w=w;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>w;
            if(w && j>i){
                e[++m].u=i;
                e[m].v=j;
                e[m].w=w;
            }
        }
    }
    sort(e+1,e+1+m);
    int ans(0),cnt(0);
    for(int i=1;i<=m;i++){
        if(find(e[i].u)!=find(e[i].v)){
            ans+=e[i].w;
            fa[find(e[i].u)]=find(e[i].v);
            cnt++;
        }
    }
    cout<<ans<<endl;
}

最小生成树讲解