【数据结构】F : 道路建设 (Ver. I)

F : 道路建设 (Ver. I)

Description

有N个村庄，编号从1到N，你应该建造一些道路，使每个村庄都可以相互连接。
两个村A和B是相连的，当且仅当A和B之间有一条道路，或者存在一个村C使得在A和C之间有一条道路，并且C和B相连。
现在一些村庄之间已经有一些道路，你的任务就是修建一些道路，使所有村庄都连通起来，并且所有道路的长度总和是最小的。

Input

测试数据有多组
第一行是整数N（3 <= N <= 100），代表村庄的数量。 然后是N行，其中第i行包含N个整数，这些N个整数中的第j个是村庄i和村庄j之间的距离（距离是[1,1000]内的整数）。
然后是整数Q（0 <= Q <= N *（N + 1）/ 2），接下来是Q行，每行包含两个整数a和b（1 <= a <b <= N），代表着村庄a和村庄b之间的道路已经建成。

Output

对于每组测试数据
输出一个整数，表示要构建的道路的长度总和最小值

Sample

Input

3
0 990 692
990 0 179
692 179 0
1
1 2

Output

179

解题思路

最小生成树啊，连接所有点并且让他们的权值之和最小，这里面需要注意的就是已经修好路的两村庄的处理，而且这还是无向图，也就是要处理两次，并且距离设为很小的数比较好。思路就是这些了，剩下的就找个prim算法或者kruscal操一下，输出最小值。

AC代码

#include <iostream>
#include <vector>
#include <limits>
using namespace std;const double MAX_WEIGHT = numeric_limits<double>::max();
const double ALREADY_CONNECTED = 1e-7;int PrimMinimumSpanningTree(const vector<vector<double>>& graph) {int n = graph.size();vector<double> key(n, MAX_WEIGHT);vector<bool> includedInMST(n, false);key[0] = 0;int totalWeight = 0;for (int count = 0; count < n; count++) {double minKey = MAX_WEIGHT;int minKeyNode = -1;for (int v = 0; v < n; v++) {if (!includedInMST[v] && key[v] < minKey) {minKey = key[v];minKeyNode = v;}}includedInMST[minKeyNode] = true;totalWeight += key[minKeyNode];for (int v = 0; v < n; v++) {if (graph[minKeyNode][v] && !includedInMST[v] && graph[minKeyNode][v] < key[v]) {key[v] = graph[minKeyNode][v];}}}return totalWeight;
}int main() {int n;while (cin >> n) {vector<vector<double>> graph(n, vector<double>(n));for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)cin >> graph[i][j];int m;cin >> m;for (int i = 0; i < m; i++) {int a, b;cin >> a >> b;graph[a - 1][b - 1] = graph[b - 1][a - 1] = ALREADY_CONNECTED;}cout << PrimMinimumSpanningTree(graph) << endl;}return 0;
}