POJ 3723 Conscription(并查集建模)

发布时间:2017-1-17 20:52:22 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"POJ 3723 Conscription(并查集建模) ",主要涉及到POJ 3723 Conscription(并查集建模) 方面的内容,对于POJ 3723 Conscription(并查集建模) 感兴趣的同学可以参考一下。

【题目链接】 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;

上一篇:throw er; // Unhandled 'error' event
下一篇:jd-gui在Ubuntu上打不开

相关文章

相关评论