LA 6807 Túnel de Rata（最大生成樹）

LA 6807 Túnel de Rata（最大生成樹）

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