题目

{% raw %}

点击显/隐题目
{% endraw %}

农夫约翰决定给他的N（1<=N<=300）个牧场浇水，这些牧场被自然的命名为1..N。
他可以给一个牧场引入水通过在这个牧场挖一口井或者修一条管道使这个牧场和一个已经有水的牧场连接。
在牧场i挖一口井的花费是w_i（1<=w_i<=100000）。
修建一条水管连接牧场i和牧场j的花费是p_ij（1<=p_ij<=100000;p_ij=p_ji;p_ii=0）。
请确定农夫约翰为了完成浇灌所有的牧场所需的最小的总花费。

{% raw %}



{% endraw %}

第1行：一个单独的整数n。
第2..n+1行：第i+1行包含一个单独的整数w_i。
第n+2..2n+1行：第n+1+i行包含n个用空可分开的整数；其中第j个数是p_ij。

{% raw %}



{% endraw %}

第1行：一个单独的整数，表示花费。

{% raw %}





{% endraw %}

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

{% raw %}



{% endraw %}

9

{% raw %}




{% endraw %}

题解

首先建成图,可以发现最终结果是把所有点都直接或间接与水相连
因此可以再建立一个源点代表水流
每个点挖井的花费就是各个点到水流的距离

这样只需要跑一遍最小生成树就行了

代码

点击显/隐代码
```cpp 挖水井 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份 #include #include #include using namespace std;

typedef long long LL;
const int maxn = 305;
int dis[maxn][maxn];
int f[maxn];
int pos;

struct Edge{
int u,v,w;
Edge(int a=0,int b=0,int c=0):u(a),v(b),w(c){}
bool operator < (const Edge &rhs)const{
return w < rhs.w;
}
}e[maxn*maxn];

int ufs(int x){
return f[x] == x ? x : f[x] = ufs(f[x]);
}
LL Kruskal(int n,int m) {
LL w = 0;
for(int i = 0; i < n; i++)
f[i] = i;
sort(e,e + m);
for(int i = 0; i < m; i++) {
int x = ufs(e[i].u),y = ufs(e[i].v);
if(x != y) {
f[x] = y;
w += e[i].w;
//cout << e[i].u << " "<<e[i].v<<" "<<e[i].w<<endl;
}
}
return w;
}

int main(){
freopen("water.in","r",stdin);
freopen("water.out","w",stdout);

cin.tie(0);
cin.sync_with_stdio(0);

pos=0;

int n;
cin>>n;
for(int i=1;i<=n;i++){
    int t;
    cin>>t;
    e[pos++] = Edge(0,i,t);
}
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++){
        int t;
        cin>>t;
        if(i<j)
            e[pos++] = Edge(i,j,t);
    }

cout << Kruskal(1+n,pos) << endl;

}

</div>