POJ-3723Conscription(最大权森林)

刚拿到这道题目一看,嗯,很简单嘛,不就是最大生成树的裸题吗,然而在输出里面却出现了错误 ∑(っ °Д °;)っ
后来仔细想了一下,发现这道题将所有的点都分为了“男”“女”两类,只有男女可能联通,而且联通可能出现圈,所以直接来是不行滴。

为了获取更多的亲密值,我们可以将所有给出的关系中的亲密值加负,同时将每对男女中的男树+n,将之放到女树之后,变成有向图,那么就不存在圈的问题啦╮(╯▽╰)╭ ,之后kruskal一下就好啦!

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 100005
int par[MAX];
int rak[MAX];
int n,m,r;
struct edge
{
    int u,v,cost;
};
edge es[MAX];
void init(int n)
{
    for(int i=0;i<=n;i++)
    {
        par[i]=i;
        rak[i]=0;
    }
}
int find(int x)
{
    if(par[x]==x)
        return x;
    else
        return par[x]=find(par[x]);
}
void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)
        return ;
    if(rak[x]<rak[y])
    {
        par[x]=y;
    }
    else
    {
        par[y]=x;
    }
    if(rak[x]==rak[y])
        rak[x]++;
}
bool same(int x,int y)
{
    return find(x)==find(y);
}
bool cmp(const edge&e1,const edge&e2)
{
    return e1.cost<e2.cost;
}
int e;
int kruskal()
{
    sort(es,es+r,cmp);
    init(MAX);
    int res=0;
    for(int i=0;i<r;i++)
    {
        edge e=es[i];
        if(!same(e.u,e.v))
        {
            unite(e.v,e.u);
            res+=e.cost;
        }
    }
    return res;
}
int x[MAX],y[MAX],d[MAX];
int main()
{
    int zu;
    scanf("%d",&zu);
    while(zu--)
    {
        scanf("%d%d%d",&n,&m,&r);
        for(int i=0;i<r;i++)
        {
            scanf("%d%d%d",&x[i],&y[i],&d[i]);
        }
        int e=n+m;//点数
        for(int i=0;i<r;i++)
        {
            es[i].u=x[i];
            es[i].v=n+y[i];
            es[i].cost=-d[i];
        }
        printf("%d\n",10000*(n+m)+kruskal());
    }
}