POJ 2377: Bad Cowtractors

概要

最大全域木を求める．

解法

辺の正負を反転して最小全域木を求める．

struct UnionFind{
    vector<int> parent, rank;
    UnionFind(int n) : parent(n,-1), rank(n, 0) { }
    int find(int x){
        if(parent[x] == -1) return x;
        else return (parent[x] = find(parent[x]));
    }
    bool unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(rank[x] < rank[y])
            parent[x] = y;
        else
            parent[y] = x;
        if(rank[x] == rank[y])
            ++rank[x];
        return true;
    }
};

typedef int Weight;
struct Edge{
    int from, to;
    Weight weight;
    Edge(int f, int t, Weight w) : from(f), to(t), weight(w) { }
};
bool operator<(const Edge &a, const Edge &b){
    return a.weight > b.weight;
}
typedef vector<Edge> Edges;

pair<Weight, Edges> kruskal_e(Edges &edges, int n){
    sort(ALL(edges)); reverse(ALL(edges));
    int sz = edges.size();
    UnionFind uf(n);
    Weight total = 0;
    Edges F;
    EACH(i, edges){
        if(uf.unite(i->from, i->to)){
            total += i->weight;
            F.push_back(*i);
        }
    }
    return make_pair(total, F);
}

int N, M;
Edges es;
int main(){
    scanf("%d%d", &N, &M);
    for(int i = 0; i < M; ++i){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        es.push_back(Edge(a, b, -c));
    }
    pair<Weight, Edges> p = kruskal_e(es, N + 1);
    printf("%d\n", p.second.size() == N - 1 ? -p.first: -1);
    return 0;
}