 |
6807 - Túnel de Rata |
题目大意：
去除图中的所有回路，且去除的边权和最小。
解题思路：
因为要使去掉的边最小，剩下的图有不能又任何回路，可以想到生成树的模型，生成树上在加边，就会构成回路。所以尽可能使得生成树上的边权最大，那么去掉的边权和就最小。用Kruskal算法可以很方便地实现。
参考代码：
#include#include #include #include using namespace std; const int MAXN = 10010; const int MAXM = 100010; struct Path { int u, v, w; bool operator < (const Path &b) { return w > b.w; } } path[MAXM]; int father[MAXN], rank_set[MAXN], s, l, sum, nCase, cCase; bool used[MAXM]; int find_set(int x) { return father[x] == x ? x : father[x] = find_set(father[x]); } void union_set(int x, int y) { int a = find_set(x), b = find_set(y); if (a == b) return; if (rank_set[a] < rank_set[b]) { father[a] = b; } else { father[b] = a; if (rank_set[a] == rank_set[b]) { rank_set[a]++; } } } void input() { scanf("%d%d", &s, &l); sum = 0; for (int i = 0; i < l; i++) { scanf("%d%d%d", &path[i].u, &path[i].v, &path[i].w); sum += path[i].w; } } void init() { for (int i = 1; i <= s; i++) { father[i] = i; rank_set[i] = 1; } memset(used, false, sizeof(used)); } void solve() { sort(path, path+l); int ans = 0; for (int i = 0; i < l; i++) { if (find_set(path[i].u) != find_set(path[i].v)) { union_set(path[i].u, path[i].v); ans += path[i].w; used[i] = true; } } int ans1 = sum - ans; for (int i = 0; i < l; i++) { if (!used[i]) { printf("Case #%d: %d %d\n", ++cCase, ans1, path[i].w); break; } } } int main() { scanf("%d", &nCase); while (nCase--) { input(); init(); solve(); } return 0; }