TYVJ P1403 [NOIP2010]关押罪犯

时间:2022-05-12 08:00:30

TYVJ的编译器总是要搞点岔子出来,上次是double必须用f输出而不能用lf,这次又不知道为何CE

于是去了洛谷P1525测试,AC

题目描述

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 号罪犯引发)。其他任何分法都不会比这个分法更优。

TYVJ P1403 [NOIP2010]关押罪犯

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

1、并查集解法

  简单又快捷,详见之前写过的题解,链接:

  http://www.cnblogs.com/SilverNebula/p/5557982.html

2、二分+二分图染色

  并不简单也并不快捷,用来练习分治算法。

  先根据罪犯间的关系建好图。

  二分在所有边权值中查找答案,每次在图中对边权大于当前所尝试答案的边进行染色,如果都染色成功,说明当前答案可行,则继续寻找更小的答案;如果染色不成功,说明当前答案不正确,则继续尝试更大的答案。

 #include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const int mxm=;
const int mxn=;
int cnt=;
int uplimit=;
int n,m;
int color[mxn];
int mid;
vector<int>eg[mxn];
vector<int>w[mxn];
struct edge{
int x,y;
int d;
}e[mxm];
int cmp(const edge a,const edge b){
return a.d>b.d;
}
void build(){//建图
for(int i=;i<=m;i++){
eg[e[i].x].push_back(e[i].y);
w[e[i].x].push_back(e[i].d);
eg[e[i].y].push_back(e[i].x);
w[e[i].y].push_back(e[i].d);
}
return;
}
bool dfs(int x,int fa){//dfs判断二分情况
if(color[x]==color[fa] && color[x]!=-)return ;//矛盾
if(color[x]==!color[fa])return ;//可行
color[x]= !color[fa];
for(int i=;i<eg[x].size();i++){
int v=eg[x][i];
if(v!=fa && w[x][i]>e[mid].d)
if(!dfs(v,x))return ;
}
return ;
}
int main(){
scanf("%d%d",&n,&m);
int i,j;
int u,v,d;
for(i=;i<=m;i++){
scanf("%d%d%d",&u,&v,&d);
e[++cnt].x=u;e[cnt].y=v;e[cnt].d=d;
}
sort(e+,e+m+,cmp);//边权从大到小排序
build();//建图
int l,r;
l=;r=m;//在所有边中二分查找
int ans=;
while(l<=r){
bool flag=;
memset(color,-,sizeof(color));//重置染色状态
color[]=;
mid=(l+r)>>;
for(i=;i<=n;i++){
if(color[i]==-)
if(dfs(i,)==false){
flag=;//不成立
break;
}
}
if(flag)r=mid-;
else{
ans=e[mid].d;//保存答案
l=mid+;//更新边界
}
}
if(m==)ans=;
printf("%d\n",ans);
return ;
}

TYVJ P1403 [NOIP2010]关押罪犯的更多相关文章

  1. 【洛谷P1525】&lbrack;NOIP2010&rsqb;关押罪犯

    关押罪犯 题目链接 思路: 二分图或并查集 这里讲并查集算法: 1.将每对罪犯的冲突关系按影响从大到小排序 2.将集合与(i+n)合并表示编号为i的罪犯不能在该集合内 3.依次从大到小处理冲突关系: ...

  2. NOIP2010关押罪犯&lbrack;并查集|二分答案+二分图染色 &vert; 种类并查集&rsqb;

    题目描述 S 城现有两座*,一共关押着N 名罪犯,编号分别为1~N.他们之间的关系自然也极不和谐.很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突.我们用“怨气值”(一个正整数值)来表示 ...

  3. noip2010 关押罪犯 (vijos1776)

    题目 S城现有两座*,一共关押着N名罪犯,编号分别为1~N.他们之间的关系自然也极不和谐.很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突.我们用“怨气值”(一个正整数值)来表示某两名罪 ...

  4. NOIP2010关押罪犯

    题目描述 S 城现有两座*,一共关押着N 名罪犯,编号分别为1~N.他们之间的关系自然也极不和谐.很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突.我们用“怨气值”(一个正整数值)来表示 ...

  5. NOIp2010 关押罪犯

    二分+2-SAT 先预处理出所有的v,然后离散化一下,在那个的基础上二分,对于每次二分出的值约束边权超过所二分出的边权的两点. //OJ 1322 //by Cydiater //2015.8.26 ...

  6. NOIP2010 关押罪犯 (并查集)

    若x,y有关系 将x与y的补集, y与x的补集建立关系 ; maxm=; ..maxm,..] of longint; f:..maxn*] of longint; i,j,m,n,x,y,z:lon ...

  7. &lbrack;noip2010&rsqb;关押罪犯 并查集

    第一次看的时候想到了并查集,但是不知道怎么实现: 标解,f[i]表示i所属的集合,用f[i+n]表示i所属集合的补集,实现的很巧妙,可以当成一个使用并查集的巧妙应用: #include<iost ...

  8. NOIP2010关押罪犯 二分&plus;二染色

    这个题一上来 没有思路,后来想没有思路就二分吧 那么我们来二分 首先,大于当前的mid值的关系,不能出现在一个集合里 (即关系形成的图是一个二分图,判定二分图可以二染色) 如果不能形成二分图,那么说明 ...

  9. tyvj P1403 关押罪犯 题解

    P1403 [NOIP2010]关押罪犯 时间: 1000ms / 空间: 131072KiB / Java类名: Main 描述    S 城现有两座*,一共关押着N 名罪犯,编号分别为1~N.他 ...

随机推荐

  1. Linux常用文件介绍

    您的一举一动都会记录在/var/log/secure 和/var/log/messages文件中

  2. android&colon;layout&lowbar;gravity 和 android&colon;gravity 的区别

    gravity 这个英文单词是重心的意思,在这里就表示停靠位置的意思. android:layout_gravity 和 android:gravity 的区别 从名字上可以看到,android:gr ...

  3. crossdomain&period;xml的配置详解

    目录 1 简介 2 crossdomain.xml的配置详解 3 总结 1 简介 flash在跨域时唯一的限制策略就是crossdomain.xml文件,该文件限制了flash是否可以跨域读写数据以及 ...

  4. ping 以及 traceroute 用法

    目的:学习linux命令ping,traceroute的用法 1:ping的用法: man ping ping:判断某个主机是否有响应 linux-8o9i:~ # 119.29.29.29 PING ...

  5. poj1008&lowbar;Maya&lowbar;Calendar

    历法的转换. #include <stdio.h> #include <math.h> #include <string.h> ][]={ "pop&qu ...

  6. Data Flow -&gt&semi;&gt&semi; Pivot

    这个组件和SQL Server的Pivot基本就是一回事.不过我观察到SSIS的Pivot只支持SUM这种聚合类型,并没有找到哪个选择可以设置聚合类型,而T-SQL语法的Pivot则支持多种聚合类型, ...

  7. Linux操作系统启动流程浅析

    启动BIOS程序 当电源键按下之后,BIOS(Basic nput Output System)就会由主板上的闪存来运行.BIOS程序会把自己解压缩到系统的内存之中,然后读取CMOS(Compleme ...

  8. Node之express

    Express 是一个简洁.灵活的 node.js Web 应用开发框架, 它提供一系列强大的特性,帮助你创建各种 Web 和移动设备应用. 如何安装: npm install -g express ...

  9. python 小程序—三级菜单—循环和字典练习

    程序中利用多级字典来存储三级菜单, 通过一系列while循环和for循环,实现了三级菜单的查询,选择,退回上级菜单,退出程序几个功能. 缺点:程序语句过于重复,效率低. #-*-coding:utf- ...

  10. java中创建多线程两种方式以及实现接口的优点

    多线程创建方式有两种 创建线程的第一种方式.继承Thread类 1.继承Thread类 2.重写Thread类中的run方法--目的将自定义代码存储在run方法.让线程执行3.调用线程的start() ...