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