Poj 2377: Bad Cowtractors

poj2377.md

Poj 2377: Bad Cowtractors

題目

分析

求最大擴張樹，一樣，Kruskal 直接用就是了

另外，該如何判斷 MST 不存在的情況呢？以下二個方法皆可行

1. 看 disjoint set 的數量是否遞減至 1
2. 看 MST 裡的邊數是否遞增至 V-1

AC Code

#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;

struct Edge {
    int u, v, cost;
    bool operator > (const Edge& e) const {
        return cost > e.cost;
    }
};

int N, M;
Edge edges[20000];

int parent[1000];
int height[1000];
void init() {
    for (int i = 0; i < N; i++) {
        parent[i] = i;
        height[i] = 0;
    }
}
int find(int a) {
    if (parent[a] == a)
        return a;
    return parent[a] = find(parent[a]);
}
void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;

    if (height[a] < height[b])
        parent[a] = b;
    else {
        parent[b] = a;
        if (height[a] == height[b])
            height[a]++;
    }
}
bool same(int a, int b) {
    return find(a) == find(b);
}

int kruskal() {
    sort(edges, edges + M, greater<Edge>());

    init();

    int group_cnt = N;
    int ans = 0;
    for (int i = 0; i < M; i++) {
        Edge& e = edges[i];
        if (!same(e.u, e.v)) {
            unite(e.u, e.v);
            ans += e.cost;
            group_cnt--;
        }
    }

    if (group_cnt != 1)
        return -1;
    return ans;
}

int main() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < M; i++) {
        int a, b, w;
        scanf("%d %d %d", &a, &b, &w);
        a--; b--;
        edges[i] = Edge{a, b, w};
    }

    printf("%d\n", kruskal());

    return 0;
}