1005. F．Snowy Roads最小生成樹Kruskal算法

Snowy Roads 最小生成樹Kruskal算法

Description   There was a heavy snow in the town yesterday. Some roads in the town are covered with thick snow so that they are hard to pass. The Snow Cleaning Team wants to make the intersections in the town connect to each other, in other words, one can walk from any intersection to any others only by passing the roads without snow. And they want the length of the snowy roads they have to clean is as short as possible. Help them to find the minimum length of the roads they must clean. Input   The first line is a positive integer T (0<T<=10), T test cases follow. For each of the test case, the first line will be three non-negative integers N (0<N<=100), the number of intersections in the town, M1 (0<=M1<=1000), the number of roads that are not covered with snow, and M2 (0<=M2<=1000), the number of roads covered with snow. The intersections are numbered from 0 to N-1. Then M1 lines follow, each of the lines contain two integers X, Y (0<=X, Y<N, X≠Y), it means that there is a road without snow between intersection X and Y. Then M2 lines follow, each of the lines contain three integers X, Y, Z (0<=X, Y<N, X≠Y, 0<Z<=1000), it means that there is a road with snow between intersection X and Y, and the team need time Z minutes to clean it. It is guaranteed that it is possible to clean some snowy roads to make all the intersections connected. And there is at most one road between two intersections. Output   For each of the test cases output only one integer in one line, the minimum length of the snowy roads they have to clean. Sample Input  Copy sample input to clipboard 3 3 0 3 0 1 4 1 2 5 2 0 6 4 3 3 2 1 0 1 2 3 3 1 1 0 3 3 0 2 2 4 3 3 3 1 1 2 2 3 0 3 7 0 2 8 0 1 9 Sample Output 9 7 題意： 有N個城市，有M1條沒有被雪覆寫的路，有M2條有被雪覆寫的路； 輸入M1組<x，y>,代表城市x到城市y的路沒有被雪覆。 輸入M2組<x, y, z>,代表城市x到城市y的路被雪覆寫的路程為z。 求周遊這N個城市需要清除被雪覆寫的最小的路程。 PS：很久之前寫過這個算法，最近複習一些資料結構知識，順便整理這個算法模闆出來。 參考《算法導論（第三版）中文版》P366 <pre name="code" class="cpp">#include <iostream> #include <vector> #include <algorithm> using namespace std; int root[101]; struct Node { int x; int y; int w; Node(int a, int b, int c) { x = a; y = b; w = c; } }; bool cmp(Node a, Node b) { return a.w < b.w; } int main() { int ncase; cin >> ncase; while (ncase--) { int n, m1, m2; int x, y, z; cin >> n >> m1 >> m2; vector<Node> v; for (int i = 0; i < m1; i++) { cin >> x >> y; v.push_back(Node(x, y, 0)); } for (int i = 0; i < m2; i++) { cin >> x >> y >> z; v.push_back(Node(x, y, z)); } for (int i = 0; i < n; i++) root[i] = i; sort(v.begin(), v.end(), cmp); int len = 0, flag = 0; for (int i = 0; i < v.size(); i++) { int x = v[i].x; int y = v[i].y; if (root[x] != root[y]) { len += v[i].w; flag++; if (flag == n - 1) break; // n個城市相連，最多為n-1條邊 int root_x = root[x]; int root_y = root[y]; for (int j = 0; j < n; j++) { if (root[j] == root_y) { root[j] = root_x; // 更新根節點 } } } } cout << len << endl; } return 0; }