POJ 3723 Conscription(并查集建模)

forever97 posted @ 2016年11月01日 20:13 in 数据结构-并查集 with tags 并查集 , 409 阅读

 

【题目链接】 http://poj.org/problem?id=3723

 

【题目大意】

    招募名单上有n个男生和m个女生,招募价格均为10000, 但是某些男女之间存在好感,则招募的时候, 可以降低与已招募人员中最大好感度的值, 求一定招募顺序使得招募总价格最小,输出最小价格

 

【题解】

    对于存在好感度的男女之间连边,那么答案就是总价格减去最大权森林

 

【代码】

#include <cstdio>
#include <algorithm>
using namespace std;
int f[20005],n,m,r,T;
struct data{int x,y,c;}p[100005];
bool cmp(data a,data b){return a.c>b.c;}
int sf(int x){return x==f[x]?x:f[x]=sf(f[x]);}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&m,&r);
        for(int i=0;i<n+m;i++)f[i]=i;
        for(int i=0;i<r;i++){
            scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].c);  
            p[i].y+=n;
        }sort(p,p+r,cmp);
        long long ans=1LL*(n+m)*10000;
        for(int i=0;i<r;i++){
            if(sf(p[i].x)==sf(p[i].y))continue;
            ans-=p[i].c;
            f[sf(p[i].x)]=sf(p[i].y);
        }printf("%lld\n",ans);
    }return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter