Luogu P1550 [USACO08OCT]打井Watering Hole

Author： YorkWu
发布时间：May 16, 2019
1132 views
No comments
797 words
Categories： OI 题目

[题目链接](https://www.luogu.org/problemnew/show/P1550 "题目链接")

* * *

这道题的思路感觉可以留下来，题目大意就是每个村能打一个井，也能挖水渠到其他村，但是需要所有村都有水，问最小花费。 \- 可以建一个虚拟节点，和每个村连起来，边权就是打水井的花费，挖水渠就正常建边。 代码：
```cpp
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    int n,fa[309];
    
    int find(int x){
        return x==fa[x]?x:fa[x]=find(fa[x]);
    }
    
    struct Edge{
        ll x,y,w;
    }e[180009];
    int tot;
    
    void add(int x,int y,int w){
        e[++tot].x=x;
        e[tot].y=y;
        e[tot].w=w;
    }
    
    bool cmp(Edge a,Edge b){
        return a.w<b.w;
    }
    
    ll kru(){
        ll ans=0,cnt=0;
        for(int i=1;i<=tot;i++){
            int xx=find(e[i].x),yy=find(e[i].y);
            if(xx==yy) continue;
            fa[xx]=yy;
            ans+=e[i].w;
            cnt++;
            if(cnt==n) break;
        }
        return ans;
    }
    
    int main(){
        cin>>n;
        for(int i=1;i<=n;i++) fa[i]=i;
        for(int i=1;i<=n;i++){
            int w;
            cin>>w;
            add(0,i,w),add(i,0,w);
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                int w;
                cin>>w;
                add(i,j,w);
            }
        }
        sort(e,e+tot+1,cmp);
        cout<<kru();
        return 0;
    }
```

Last modification：March 14, 2020