题意:有一种叫作Pseudoforest的结构,表示在无向图上,每一个块中选取至多包含一个环的边的集合,又称“伪森林”。问这个集合中的所有边权之和最大是多少?
分析:如果没有环,那么构造的就是最大生成森林,在此基础上,只要取每个块中剩余边的最大边,必然得到结果。不过要构造出每条边归属于哪个块。
看了别人的代码,发现原来可以直接构造出一个标记数组记录环,在做并查集的时候扩充if(find(u)==find(v))这一条件,可以直接得到结果。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; const int MAXN=;
const int MAXM=; struct Edge{
int u,v,c;
}edge[MAXM]; int p[MAXN],is[MAXN]; int cmp(Edge a,Edge b)
{
return a.c>b.c;
} void init(int n)
{
for(int i=;i<n;i++)
{
is[i]=;
p[i]=i;
}
} int Find(int x)
{
return p[x]==x?x:p[x]=Find(p[x]);
} int check(int u,int v,int c)
{
int fu=Find(u);
int fv=Find(v);
if(fu==fv){
if(is[fu])
return ;
is[fu]=;
return ;
}
if(is[fu]&&is[fv])
return ;
if(is[fu])
p[fv]=fu;
else
p[fu]=fv;
return ;
} int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
if(!n&&!m)
return ;
for(int i=;i<m;i++)
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].c);
sort(edge,edge+m,cmp); int ans=;
init(n);
for(int i=;i<m;i++)
{
if(check(edge[i].u,edge[i].v,edge[i].c))
ans+=edge[i].c;
}
printf("%d\n",ans);
}
return ;
}
/*
5 6
0 1 4
1 2 5
0 2 3
0 3 2
3 4 3
3 4 2
*/