洛谷P1550打井

打井

题目

该题是一个最小生成树的好题，但是比起一般的最小生成树来说他不仅仅有各个井相连，而且还要和地下水相连，所以地下水我们也可以看成一口井。

代码

#include <bits/stdc++.h>
using namespace std;
struct edge {
	int a, b, c;
}e[100100];
bool cmp(const edge &a, const edge &b)
{
	return a.c < b.c;
}
int cnt, fa[100100], vis[1000][1000], ans;int n, m;
int find(int a)
{
	if (fa[a] == a)
		return a;
	return fa[a] = find(fa[a]);	
} 
int main()
{
 	
 	scanf("%d", &n);
 	for (int i = 1; i <= n; i++)
 	{
 		scanf("%d", &e[++m].c);
 		e[m].a = 0, e[m].b = i;
 	}
 	for (int i = 1; i <= n; i++)
 		for (int j = 1; j <= n; j++)
 		{
 			int a;
 			scanf("%d", &a);
 			if (!vis[i][j] || !vis[j][i])
 			{
 				vis[i][j] = vis[j][i] = 1;
 				e[++m].a = i, e[m].c = a, e[m].b = j;		
 			}
 		}
   	sort(e + 1, e + 1 + m, cmp);
  	for (int i = 0; i <= n; i++)
  		fa[i] = i;
 	for (int i = 1; i <= m; i++)
 	{
 		if (cnt == n)
 			printf("%d", ans), exit(0);
  		if (find(e[i].a) != find(e[i].b))
   		{
  			fa[find(e[i].a)] = find(e[i].b);
  			ans += e[i].c;
  		// 	printf ("%d %d %d
", e[i].b, e[i].a, e[i].c);
 			cnt++;
  		}
  	}
}