hdu3367Pseudoforest (最大生成树之kruskal 算法)

Problem Description In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. The maximal pseudoforests of G are the pseudoforest subgraphs of G that are not contained within any larger pseudoforest of G. A pesudoforest is larger than another if and only if the total value of the edges is greater than another one’s.

Input The input consists of multiple test cases. The first line of each test case contains two integers, n(0 < n <= 10000), m(0 <= m <= 100000), which are the number of the vertexes and the number of the edges. The next m lines, each line consists of three integers, u, v, c, which means there is an edge with value c (0 < c <= 10000) between u and v. You can assume that there are no loop and no multiple edges.
The last test case is followed by a line containing two zeros, which means the end of the input.

Output Output the sum of the value of the edges of the maximum pesudoforest.

Sample Input

Sample Output

3
5

Source “光庭杯”第五届华中北区程序设计邀请赛暨 WHU第八届程序设计竞赛

这题题意理解了好一阵子才明白,  给出一个图，要求出最大的pseudoforest， 所谓pseudoforest就是指这个图的一个子图，这个子图的每个连通分量中最多只能有一个环， 而且这个子图的所有权值之和最大。这个就是所谓的伪森林。

过程类似与kruskal求最小生成树，千万不要直接求最大生成树，一开始时我想到的方法是用kruskal算法求出这个图的最大生成树， 然后给这一棵数再加上一条最大的边，构成一个环。 但是WA得快吐血了。

正确的做法和求最大生成树很类似，但是有一点改变， 因为每个连通分量允许有一个回环， 所以，我们可以在进行合并两颗树时，要判断这两颗树是否有回环，如果两个树都有回环，那么明显不可以合并这两颗树， 如果只有一棵树有回环，那么可以合并，然后标上记号。如果两个都没有回环，那么就直接合并了。
如果有两个点是属于同一棵树上的，那么判断这棵树上是否已有回环，如果没有的话，那么允许有一个回环，可以链接这两点，再标上记号。

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef struct nn
{
    int x,y,p;
}Node;
Node edg[100005];
int fath[10005],sum,cycle[10005];//cycle[]标记树有没有环
int cmp(Node a,Node b)//用于sort排序时的标准
{
    return a.p>b.p;//从大到小排
}
void set_first(int n)//设制初始化
{
    for(int i=0;i<n;i++)
    {
        fath[i]=i; cycle[i]=0;
    }
}
int find_fath(int x)//找根节点时，路径压缩
{
    if(x!=fath[x])
    fath[x]=find_fath(fath[x]);
    return fath[x];
}
void kruskal(int n,int m)//n为点数，m为边数
{
    int a,b,k=0;
    sum=0;
    set_first(n);//初始化
    sort(edg,edg+m,cmp);//从大到小排序
    for(int i=0;i<m;i++)
    {
        a=find_fath(edg[i].x);
        b=find_fath(edg[i].y);
        if(a!=b&&(cycle[a]!=1||cycle[b]!=1))//如果这两棵树都有环，那么不能合并
        {
            sum+=edg[i].p;
            fath[a]=b; 
            if(cycle[a]) cycle[b]=cycle[a];//当合并时，注意环的标记是要相传的
        }
        else if(cycle[a]==0)//当两个点都在一棵树上并且树还没有环时，这棵树添一个边构成环
        {
           sum+=edg[i].p; cycle[a]=1;//并且标记这棵树有环，1表示有环
        }
    }
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)>0&&n+m!=0)
    {
        for(int i=0;i<m;i++)
        scanf("%d%d%d",&edg[i].x,&edg[i].y,&edg[i].p);
        kruskal(n,m);
        printf("%d\n",sum);
    }
}

秒客网

hdu3367Pseudoforest (最大生成树之kruskal 算法)

相关文章