洛谷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\n", e[i].b, e[i].a, e[i].c);

 			cnt++;

  		}

  	}

}

巴特西

洛谷P1550打井

最新文章

热门文章