题解-灌溉(未完成）

To The Sun

2026-05-16 19:15:41

发布于：上海

7阅读

0回复

0点赞

我觉得这道题很特殊。

Watering Hole G

题目大意：
一共有n块农田。每块田水打井所需要的费用是 $w[i]$ ，将第i块田和第j块田连接起来的费用是 $a[i][j]$ 。
问使得所有土地都有水用需要多少钱。

一块田有两种可能：1.独立建立水井 2.跟与水井有联系（有水井或者与水井相连）的水井连接

大部分会最小生成树的人第一反应可能是：求出所有田地的最小生成树。最后找一个打水井最便宜的田打上水井。

但是如果，有田单独打水井的费用比去连接别的田的费用便宜很多呢。
我们如何判断一块田是应该打水井还是应该与别的边做联系呢。

这个时候有一个很妙的方法：我们将”水源“看作一个点。每个其他的点都与它建立一条边，边权就是打水井的费用。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct Node{
	int x,y,z;
}node[N];
int c[N];
bool cmp(Node a,Node b){
	return a.z<b.z;
}
int f(int x){
	return (x==c[x])?x:c[x]=f(c[x]);
}
typedef long long ll;
int main(){
	int n;
	cin>>n;
	int now=0;
	for(int i=1;i<=n;i++){
		int w;
		cin>>w;
		node[++now]={0,i,w};
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int x;
			cin>>x;
			node[++now]={i,j,x};
		}
	}
    for(int i=1;i<=n;i++)c[i]=i;
	sort(node+1,node+1+now,cmp);
	ll ans=0;
	for(int i=1;i<=now;i++){
		int p=f(node[i].x),q=f(node[i].y);
		if(p==q)continue;
		c[p]=q;
		ans+=node[i].z;
	}
	cout<<ans;
	return 0;
}