hdu3367 Pseudoforest（最大生成树+伪森林）

http://acm.hdu.edu.cn/showproblem.php?pid=3367

题意：给你一个森林和一些边，求它的最大生成树。这个生成树里允许至多有一个环。

思路：本题点数过多，不能用Prim。至于最大生成树，其实就是改变下排序顺序而已。关键是对伪森林的操作，允许至多有一个环。刚开始想的添加一个节点就判断是否可以构成环，然后能构成环的话把这个边存起来往复求最大值，最后找到最大值的边即为伪森林所需的最大边。

接着就开始WA。没思路，看别人的，对MST的理解更进了一步。所谓生成MST的过程，其实就是森林变成树的过程，原先没环直接合并即可。现在有环，那么合并的两个节点就要分情况讨论了：

(1)、如果这两个节点不在同一棵树，看这两个节点所在的树中是否有环。初始设置所有树均为无环树。如果都没有，那么直接合并；如果有一个，合并后把这个树置为有环树；如果都有，那么不满足至多一个环，不合并。

(2)、如果这两个节点不在同一棵树，看这两个节点所在的树中是否有环。初始设置所有树均为无环树。如果都没有，那么直接合并，并且置为有环树；如果有一个或其他，那么不满足至多一个环，不合并。

#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <queue>

using namespace std;

typedef long long LL;

const int N = 10005;
const int INF = 0x3f3f3f3f;

int pre[N], n, ednum, sum;
bool circle[N];

struct node
{
    int u, v, w;
}edge[100005];

bool cmp(node x, node y)
{
    if(x.w>y.w) return true;
    else return false;
}

int Find(int x)
{
    int r = x;
    while(r != pre[r])
        r = pre[r];
    int i = x, j;
    while(pre[i] != r)
    {
        j = pre[i];
        pre[i] = r;
        i = j;
    }
    return r;
}

void Union(int p1, int p2, int w)
{
    int x = Find(p1);
    int y = Find(p2);
    if(x != y)//不在同一棵树上
    {
        if(circle[x]==false && circle[y]==false)//两棵树都没有环
        {
            pre[x] = y;
            sum+=w;
        }
        else if((circle[x]==true&&circle[y]==false) || (circle[x]==false&&circle[y]==true))//一棵树有环
        {
            pre[x] = y;
            sum+=w;
            circle[y] = true;
        }
    }
    else//在同一棵树上
    {
        if(circle[x]==false && circle[y]==false)//两棵树都没有环
        {
            pre[x] = y;
            sum+=w;
            circle[y] = true;
        }
    }
}

void kruskal()
{
    for(int i = 0; i < n; i++)//起点坐标可以是0
    {
        pre[i] = i;
    }
    memset(circle, false, sizeof(circle));
    sort(edge+1, edge+1+ednum, cmp);
    for(int i = 1; i <= ednum; i++)
    {
        Union(edge[i].u, edge[i].v, edge[i].w);
    }
}


int main()
{
  //  freopen("in.txt", "r", stdin);
    int u, v, w;
    while(~scanf("%d%d", &n, &ednum))
    {
        if(n==0 && ednum==0) break;
        sum = 0;
        for(int i = 1; i <= ednum; i++)
        {
            scanf("%d%d%d", &u, &v, &w);
            edge[i] = (struct node){u, v, w};
        }
       // prim();
        kruskal();
        printf("%d\n", sum);
    }
    return 0;
}