文档章节

CODEVS 1069 关押罪犯

LOI_xczhw
 LOI_xczhw
发布于 2016/10/30 09:57
字数 403
阅读 7
收藏 0

屠龙宝刀点击就送
作为2010年这种神题库的压轴的大题,这道题难度却不如另外几道……
题目大意:
有两座监狱,一堆人,有的人有关系,如果有关系的两个人ai,bi在同一座监狱里,就会产生ci坏的影响。然后你的boss就会很不爽,于是乎,你就想着,让最坏的影响尽量小,求是多少(最小化最大值)
输入描述:
第一行 罪犯的数目,边的数目
i + 1行 ai bi ci
输出描述:
ans
样例:
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
输出:
3512
扩展域的并查集,(一眼题……?)
1~n 表示 和某点在同一监狱里,n+1~(n << 1)表示和某点不在同一监狱里
solved!!

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 100000 + 5;
int fa[MAXN * 2];
int n,m;
struct edge
{
    int f,t,v;
}l[MAXN];
void init()
{
    for(int i = 1;i <= n * 2;i ++)
        fa[i] = i;
    return;
}
int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
bool same(int x,int y)
{
    return find(x) == find(y);
}
void merge(int x,int y)
{
    x = find(x);
    y = find(y);
    fa[x] = y;
    return;
}
bool cmp(edge a,edge b)
{
    return a.v > b.v;
}
int main()
{
    scanf("%d %d",&n,&m);
    init();
    for(int i = 1;i <= m;i ++)
        scanf("%d %d %d",&l[i].f,&l[i].t,&l[i].v);
    sort(l + 1,l + m + 1,cmp);
    for(int i = 1;i <= m;i ++)
    {
        if(same(l[i].f,l[i].t))
        {
            printf("%d\n",l[i].v);
            return 0;
        }
        merge(l[i].f,l[i].t + n);
        merge(l[i].t,l[i].f + n);
    }
    puts("0");
    return 0;
}

有点懒,没写启发(才不是为了压代码呢……)

© 著作权归作者所有

LOI_xczhw
粉丝 1
博文 79
码字总数 42567
作品 0
莱芜
私信 提问
BUF早餐铺 亚马逊面部识别误将国会议员识别为罪犯;推特下架超过14万违反隐私政策的APP;在押囚犯利用平板漏洞窃取22.5万美元数字资产

  各位Buffer早上好,今天是2018年7月30日星期五,农历六月十八。今天份的BUF早餐内容有:亚马逊面部识别误将国会议员识别为罪犯;推特下架超过14万违反隐私政策的APP;在押囚犯利用平板漏...

FreeBuf
2018/07/30
0
0
如何开启Windows 7系统的上帝模式?

Windows 7系统隐藏着许多小秘密,其中就有被炒得沸沸扬扬,传得神乎其神的“God Mode”(上帝模式),Win7系统的“上帝模式”里面包含Windows 7系统的所有设置,让用户操作更简单而已。它将控制...

一个敲代码的前端妹子
2018/06/30
0
0
splay的各种操作与简易讲解

基本操作 插入 和二叉查找树一样,但是插入完成后要splay一下(即伸展),伸展操作下面有 伸展 查找前驱或后驱 例题:codevs1285/洛谷P2286/bzoj1208 宠物收养所 删除和合并 先把要删除的点s...

litble
2017/07/07
0
0
洛谷P1525 关押罪犯 【思维 + 二分图判定】

版权声明:本文为博主原创文章,喜欢就点个赞吧 https://blog.csdn.net/Anxdada/article/details/82831861 传送门 题意: 给出m对憎恨关系, 有一个憎恨值, 现在要将这n个人分成两堆人, 要求这...

Anxdada
2018/09/24
0
0
关于2018年安全威胁趋势 赛门铁克这么说

  【IT168 资讯】转眼间,2017年已经接近尾声,马上我们将迎来2018崭新的一年,对于网络安全来讲,2017年是不寻常的一年,这一年各种网络攻击不断,尤其WannaCry勒索软件攻击的影响一度波及...

it168网站
2017/12/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OpenStack 简介和几种安装方式总结

OpenStack :是一个由NASA和Rackspace合作研发并发起的,以Apache许可证授权的自由软件和开放源代码项目。项目目标是提供实施简单、可大规模扩展、丰富、标准统一的云计算管理平台。OpenSta...

小海bug
昨天
5
0
DDD(五)

1、引言 之前学习了解了DDD中实体这一概念,那么接下来需要了解的就是值对象、唯一标识。值对象,值就是数字1、2、3,字符串“1”,“2”,“3”,值时对象的特征,对象是一个事物的具体描述...

MrYuZixian
昨天
6
0
数据库中间件MyCat

什么是MyCat? 查看官网的介绍是这样说的 一个彻底开源的,面向企业应用开发的大数据库集群 支持事务、ACID、可以替代MySQL的加强版数据库 一个可以视为MySQL集群的企业级数据库,用来替代昂贵...

沉浮_
昨天
6
0
解决Mac下VSCode打开zsh乱码

1.乱码问题 iTerm2终端使用Zsh,并且配置Zsh主题,该主题主题需要安装字体来支持箭头效果,在iTerm2中设置这个字体,但是VSCode里这个箭头还是显示乱码。 iTerm2展示如下: VSCode展示如下: 2...

HelloDeveloper
昨天
7
0
常用物流快递单号查询接口种类及对接方法

目前快递查询接口有两种方式可以对接,一是和顺丰、圆通、中通、天天、韵达、德邦这些快递公司一一对接接口,二是和快递鸟这样第三方集成接口一次性对接多家常用快递。第一种耗费时间长,但是...

程序的小猿
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部