题解 | #Watering Hole#

这题比较水。

首先考察点就是最小生成树，对吧？

然后水管相当于一条边

然后每个点可以建立井，那么就新加一个大源点，所有点往大源点连一条边即可

边权就是W[i]

#include<bits/stdc++.h>
using namespace std;
#define s 406
#define ll long long
struct node{
	int x,y,w;
	bool operator <(const node&u)const{
		return w>u.w;
	}
};
int fa[500];
int Get(int x){
	if(fa[x]==x)return x;
	return fa[x]=Get(fa[x]);
}
int main(){
	priority_queue<node>q;
	int n;
	cin>>n;
    fa[s]=s;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		fa[i]=i;
		q.push({s,i,x});
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int x;
			cin>>x;
			q.push({i,j,x});
		}
	}
	ll res=0;
	while(q.empty()==false){
		int x=q.top().x,y=q.top().y,w=q.top().w;
		q.pop();
		int rx=Get(x),ry=Get(y);
		if(rx==ry)continue;
		fa[rx]=ry;
		res+=w;
	}
	cout<<res;
	return 0;
}