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