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;
}
)
