POJ 3723




【类型】

并查集优化kruskal

【Tip】

并查集使得可以判断任意两点是否可归溯于同一点,藉此来判断若链接两点是否会形成一个环.

这道题的输入是两个人以及两个人之间的亲密关系,征募某个人的花费为10000-(已征募人中亲密关系和自己的最大值).

这里我们在每征募某个人a时,若使用了a,b的关系,就连一条a,b的边。

如果这个图中存在圈,则一定会出现矛盾(谁是第一个被征募的?).

所以这个图一定是森林.

把人看做顶点.关系看做边,则这个问题就可以转化为求解无向图中的最大权森林问题(即亲密度之和最大),最大权森林问题可以通过把所有边权取反来求最小生成树.

【Code】

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int MAX_N=60000;
struct edge{
    int u,v,cost;
};

bool comp(const edge& e1,const edge& e2){
    return e1.cost<e2.cost;
}

edge es[MAX_N];
int V,E;//顶点数和边数

//并查集
int par[MAX_N];//父亲
int rank[MAX_N];//树的高度

void init_union_find(int n){
    for(int i=0;i<n;++i){
        par[i]=i;
        rank[i]=0;
    }
}

//查询树的根
int find(int x){
    if(par[x]==x){
        return x;
    }else{
        return par[x]=find(par[x]);
    }
}

//合并x和y所属集合
void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y) return;

    if(rank[x]<rank[y]){
        par[x]=y;
    }else{
        par[y]=x;
        if(rank[x]==rank[y]) rank[x]++;
    }
}

//判断x和y是否属于同一个集合
bool same(int x,int y){
    return find(x)==find(y);
}

int kruskal(){
    sort(es,es+E,comp);
    int res=0;
    init_union_find(V);
    for(int i=0;i<E;++i){
        edge e=es[i];
        if(!same(e.u,e.v)){
            unite(e.u,e.v);
            res+=e.cost;
        }
    }
    return res;
}

int main(){
    int N;
    scanf(“%d”,&N);
    while(N–){
        int B,G,R;
        scanf(“%d%d%d”,&G,&B,&R);
        V=G+B;
        E=R;
        for(int i=0;i<R;++i){
            int a,b,c;
            scanf(“%d%d%d”,&a,&b,&c);
            es[i]=(edge){a,G+b,-c};
        }
        printf(“%d\n”,10000*(V)+kruskal());
    }

    return 0;
}