正文
【hdu3367】Pseudoforest（伪森林）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
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 = ; i <= n; i++)
{
parent[i] = -;
mark[i] = false;
}
}
int find(int x)
{
if (parent[x] < )
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 == && m == )
return ;
djs::init();
edges.clear();
int a, b, c;
for (int i = ; i <= m; i++)
{
cin >> a >> b >> c;
edges.push_back((edge){a, b, c});
}
sort(edges.begin(), edges.end(), cmper); int ans = ;
for (int i = ; i < edges.size(); i++)
{
if (djs::merge(edges[i].from, edges[i].to))
ans += edges[i].weight;
}
cout << ans << endl;
}
return ;
}
