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

F : 道路建设 (Ver. I)

Des c ription

有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

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

Sa mple

Input

Output

解题思路

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

AC代码

#include <iostream&gt;
#include <vector&gt;
#include <limits&gt;
using namespace std;

const double MAX_WEIGHT = numeric_limits<double&gt;::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;
}