MyException - 我的异常网
当前位置:我的异常网» C++ » 洛谷看押罪犯,并查集

洛谷看押罪犯,并查集

www.MyException.Cn  网友分享于:2013-09-07  浏览:0次
洛谷关押罪犯,并查集

题目描述

S 城现有两座监狱,一共关押着N 名罪犯,编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突。我们用“怨气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一监狱,他们俩之间会发生摩擦,并造成影响力为c 的冲突事件。

每年年末,警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表,然后上报到S 城Z 市长那里。公务繁忙的Z 市长只会去看列表中的第一个事件的影响力,如果影响很坏,他就会考虑撤换警察局长。

在详细考察了N 名罪犯间的矛盾关系后,警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配,以求产生的冲突事件影响力都较小,从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨,那么他们一定会在每年的某个时候发生摩擦。

那么,应如何分配罪犯,才能使Z 市长看到的那个冲突事件的影响力最小?这个最小值是多少?

输入输出格式

输入格式:

 

输入文件的每行中两个数之间用一个空格隔开。第一行为两个正整数N 和M,分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的M 行每行为三个正整数aj,bj,cj,表示aj 号和bj 号罪犯之间存在仇恨,其怨气值为cj。数据保证1<aj=<=bj<=N ,0 < cj≤ 1,000,000,000,且每对罪犯组合只出现一次。

 

输出格式:

 

共1 行,为Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件,请输出0。

 

输入输出样例

输入样例#1:
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
输出样例#1:
3512

说明

【输入输出样例说明】罪犯之间的怨气值如下面左图所示,右图所示为罪犯的分配方法,市长看到的冲突事件影响力是3512(由2 号和3 号罪犯引发)。其他任何分法都不会比这个分法更优。

【数据范围】对于30%的数据有N≤ 15。对于70%的数据有N≤ 2000,M≤ 50000。对于100%的数据有N≤ 20000,M≤ 100000。

 

思路:并查集的一个模版,先按怒气值从大到小排序(贪心思想)然后再一一拆散它们,如果不能拆散了,就输出它们当前的怒气值,over

具体的代码上有注释哦!!!

//Gang
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#define FOR(x,y,z) for(int x=y;x<=z;x++)
#define REP(x,y,z) for(int x=y;x>=z;x--)
#define ll long long
using namespace std;
int n,m;
int per[100005];
int fa[300000];
struct node//定义一个结构体 方便排序 
{
    int a,b,c;
} e[100005];
int cmp(node Q,node W)//结构体排序,必须定义排序规则 
{
    return Q.c>W.c;
}
int find(int x)
{
    return x==fa[x]?x:fa[x]=find(fa[x]);//递归写法 寻找根节点 
}

int main()
{
    scanf("%d%d",&n,&m);
    FOR(i,1,n*2)//2*n相当于拓展出两个监狱来关押罪犯。 
    fa[i]=i;//起初,每个罪犯的父亲都是他自己 
    FOR(i,1,m)
    scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c); 
    sort(e+1,e+m+1,cmp);
    FOR(i,1,m)
    {
        int x=find(e[i].a),y=find(e[i].b);
        if(x==y)//如果实在没办法拆散两个有怒气值的罪犯,即它们的父节点相同(在同一个监狱),就输出他们当前的怒气值 
        {
            printf("%d\n",e[i].c);
            return 0;//结束程序 
        }
        fa[x]=find(e[i].b+n);//敌人的敌人就是自己的朋友 
        fa[y]=find(e[i].a+n);//敌人的敌人就是自己的朋友 
    }
    printf("0\n"); //如果没有在一起有怒气值的罪犯,就输出0哦 
    return 0;
}

 

文章评论

编程语言是女人
编程语言是女人
程序员和编码员之间的区别
程序员和编码员之间的区别
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
旅行,写作,编程
旅行,写作,编程
我的丈夫是个程序员
我的丈夫是个程序员
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
那些争议最大的编程观点
那些争议最大的编程观点
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
程序员必看的十大电影
程序员必看的十大电影
10个调试和排错的小建议
10个调试和排错的小建议
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
中美印日四国程序员比较
中美印日四国程序员比较
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
一个程序员的时间管理
一个程序员的时间管理
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
程序员都该阅读的书
程序员都该阅读的书
每天工作4小时的程序员
每天工作4小时的程序员
Java程序员必看电影
Java程序员必看电影
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
鲜为人知的编程真相
鲜为人知的编程真相
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
代码女神横空出世
代码女神横空出世
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
如何成为一名黑客
如何成为一名黑客
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
程序员的鄙视链
程序员的鄙视链
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
总结2014中国互联网十大段子
总结2014中国互联网十大段子
我是如何打败拖延症的
我是如何打败拖延症的
为什么程序员都是夜猫子
为什么程序员都是夜猫子
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
程序员应该关注的一些事儿
程序员应该关注的一些事儿
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
 程序员的样子
程序员的样子
老程序员的下场
老程序员的下场
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有