农田引水

问题描述

农田有 n 块，编号从 1~n。种田要灌水。
众所周知东东是一个魔法师，他可以消耗一定的 MP 在一块田上施展魔法，使得黄河之水天上来。他也可以消耗一定的 MP 在两块田的渠上建立传送门，使得这块田引用那块有水的田的水。(1 ≤ n ≤ 300)
黄河之水天上来的消耗是 Wi，i 是农田编号 (1 ≤ Wi ≤ 1e5)
建立传送门的消耗是 Pij，i、j 是农田编号 (1 ≤ Pij ≤ 1e5, Pij = Pji, Pii = 0)
求为所有的田灌水的最小消耗。

Input

第 1 行：一个数 n
第 2 行到第 n + 1 行：数 wi
第 n + 2 行到第 2n + 1 行：矩阵即 pij 矩阵

Output

最小消耗的MP值

Sample

Input: 
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

Output: 
9

Limitation

Time limit		1000 ms
Memory limit	262144 kB

解题思路

可以将“天上来”作为源点，即第0号农田到第 i 号农田灌水需要消耗的MP值，因此样例的数组可变成：

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

本题就变成了最小生成树问题，可以用Kruskal算法:
将所有的边按边权升序排列，每次加入最小权的边到生成树中，保证加入的边在该连通图中，且不会生成环，直到最小生成树中的边数等于总顶点数减1。

这些权重之和就是答案。

源代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int maxN = 305;

struct edge {
	int u, v, w;
	edge(int _u, int _v, int _w) :u(_u), v(_v), w(_w) {  }
};

bool cmp(edge a, edge b) {
	return a.w < b.w;
}

int par[maxN];

int find(int x) {
	if (par[x] == x)
		return x;
	return par[x] = find(par[x]);
}

int kruskal(int n, vector<edge> v) {
	int ans = 0;
	int edgeCount = 0;
	for (int i = 0; i <= n; i++)
		par[i] = i;
	sort(v.begin(), v.end(), cmp);

	for (int i = 0; i != v.size(); i++) {
		int p1 = find(v[i].u);
		int p2 = find(v[i].v);
		if (p1 != p2) {//并查集保证不会生成环
			par[p1] = p2;
			ans += v[i].w;
			edgeCount++;
			if (edgeCount == n)
				break;
		}
	}

	return ans;
}

int main() {
	int n;
	cin >> n;
	vector<edge> v;
	for (int i = 1; i <= n; i++) {
		int a;
		cin >> a;
		edge e1(0, i, a);
		edge e2(i, 0, a);
		v.push_back(e1);
		v.push_back(e2);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int a;
			cin >> a;
			if (a != 0) {
				edge e(i, j, a);
				v.push_back(e);
			}
		}
	}
	int res = kruskal(n, v);
	cout << res << endl;
	return 0;
}