hdu 3367 Pseudoforest（并查集）

题意：有一种叫作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

 */

巴特西

hdu 3367 Pseudoforest（并查集）

最新文章

热门文章