P1550 [USACO08OCT] Watering Hole G

原题链接

题解

最小生成树的应用。这道题多转了一个弯，这道题其实多了一个结点（代表一个虚拟水井），每块田打井的费用可以过渡到从虚拟水井运水的费用，然后再套用最小生成树的模板即可。

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node{
    int from,to,value;
};
int father[305],n;
Node a[90005];
void build(){
    for (int i=0;i<=n;i++) father[i]=i;
}
bool cmp(Node a,Node b){
    return a.value<b.value;
}
int find(int i){
    if (father[i]!=i)
        father[i]=find(father[i]);
    return father[i];
}
int main(){
    int r=0;
    ll sum=0;
    cin>>n;
    build();
    for (int i=1;i<=n;i++){
        int x;
        cin>>x;
        a[r].from=0;
        a[r].to=i;
        a[r++].value=x;
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++){
            int x;
            cin>>x;
            if (j<i){
                a[r].from=i;
                a[r].to=j;
                a[r++].value=x;
            }
        }
    sort(a,a+r,cmp);
    for (int i=0;i<r;i++){
        int fx=find(a[i].from),fy=find(a[i].to);
        if (fx!=fy){
            father[fx]=fy;
            sum+=(ll)a[i].value;
        }
    }
    cout<<sum<<endl;
    return 0;
}