http://acm.hdu.edu.cn/showproblem.php?pid=3367
伪森林就是一个无向图，这个无向图有多个连通块且每个连通块只有一个简单环。
给你一个无向图，让你找这个图的一个最大生成伪森林（即边权之和最大）。
考虑到用Kruscal算法搞最大生成树时，每次加入一条边之前都必须保证边的这两点在之前属于两个连通块，就是为了防止出现环。
即如果加入的边的两点在一个没有环的连通块里的话，就会出现一个环。
那么我们把Kruscal算法改造一下，如果这条边的两点在同一个没有环的连通块的话，仍然加入这条边，并把这个连通块标记有环。把所有的边都试着加入一遍后就可以得到最终答案。
还要注意如果这条边的两点在不同的连通块，但是两个连通块都有环，那么这条边也不能加。
#include <iostream> #include <vector> #include <algorithm> #define maxn 10005 using namespace std; int n, m; namespace djs { int parent[maxn]; bool mark[maxn]; void init() { for (int i = 0; i <= n; i++) { parent[i] = -1; mark[i] = false; } } int find(int x) { if (parent[x] < 0) return x; else return parent[x] = find(parent[x]); } bool merge(int x, int y) { x = find(x); y = find(y); if (x != y) // x与y不在一个连通块 { if (mark[x] && mark[y]) // 两个连通块都有环 return false; else { if (parent[x] > parent[y]) swap(x, y); parent[x] += parent[y]; parent[y] = x; mark[x] |= mark[y]; return true; } } else // x与y在一个连通块 { if(mark[x]) return false; else // 这个连通块没有环，可以加这条边 { mark[x] = true; return true; } } } } struct edge { int from, to, weight; }; inline bool cmper(const edge &x, const edge &y) { return x.weight > y.weight; } vector<edge> edges; int main() { while (true) { cin >> n >> m; if (n == 0 && m == 0) return 0; djs::init(); edges.clear(); int a, b, c; for (int i = 1; i <= m; i++) { cin >> a >> b >> c; edges.push_back((edge){a, b, c}); } sort(edges.begin(), edges.end(), cmper); int ans = 0; for (int i = 0; i < edges.size(); i++) { if (djs::merge(edges[i].from, edges[i].to)) ans += edges[i].weight; } cout << ans << endl; } return 0; }
原文：http://www.cnblogs.com/ssttkkl/p/7565251.html