洛谷 P1525 关押罪犯 (贪心,扩展域并查集)
2024-09-29 23:40:13
题意:有\(n\)个罪犯,\(m\)对罪犯之间有仇,现在将这些罪犯分到两个监狱里去,问两个监狱里有仇罪犯之间的最大权值最小为多少.
题解:先按边权从大到小排序,然后贪心,边权大的两个罪犯,我们一定要先让他们两人分到不同的监狱中,这里我们就可以用并查集来维护, 用种类并查集每次维护两个罪犯的关系,如果他们不在同一集合,就将他们合并到两个不同的集合,
如果他们在同一个集合,那么就直接输出他们的权值.
代码:
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define db double
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;} inline int read()
{
int X=0; bool flag=1; char ch=getchar();
while(ch<'0'|ch>'9') {if(ch=='-') flag=0; ch=getchar();}
while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;
return ~(X-1);
} struct misaka{
int x,y,val;
bool operator < (const misaka & mikoto) const{
return val>mikoto.val;
}
}e[N]; int n,m;
int p[N]; int find(int x){
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
} int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m; rep(i,1,m){
cin>>e[i].x>>e[i].y>>e[i].val;
} sort(e+1,e+1+m); rep(i,1,2*n+10) p[i]=i; rep(i,1,m){
int x=e[i].x;
int y=e[i].y;
if(p[find(x)]==p[find(y)] || p[find(x+n)]==p[find(y+n)]){
cout<<e[i].val<<'\n';
return 0;
}
p[find(x)]=p[find(y+n)];
p[find(x+n)]=p[find(y)];
} cout<<0<<'\n'; return 0;
}
最新文章
- NFS Volume Provider(Part I) - 每天5分钟玩转 OpenStack(62)
- knockoutjs+ jquery pagination+asp.net web Api 实现无刷新列表页
- Mvc利用淘宝Kissy uploader实现图片批量上传附带瀑布流的照片墙
- 【分布式协调器】Paxos的工程实现-cocklebur简介(一)
- bootstrap学习笔记<;十>;(按钮组,导航)
- Nwjs从入门到精通 菜鸟实践笔记【1】
- H3C HCSE 官方培训胶片(中文) 下载
- Java 多态 父类和子类方法的访问控制权限
- 简单分析下用yii2的yii\helpers\Html类和yii.js实现的post请求
- JVM内存结构(转)
- c++ 远程连接局域网内 数据库,并进行操作
- MiZ702学习笔记8——让MiZ702变身PC的方法
- Could not resolve com.android.support:appcompat-v7:28.0.0 错误处理
- spring实现定时任务的两种方式
- 戴尔 Latiteude E7240 i7-4600U
- [转] Foobar2000 DSP音效外挂元件-Part4
- 读取Excel表格日期类型数据的时候
- 【Debian】install
- Inno Setup入门(十五)——Inno Setup类参考(1)
- Eclipse+ADT+Android SDK 搭建安卓开发环境(转)
热门文章
- 实现strStr
- 【Git】3、创建Git版本库、配置Git仓库用户邮箱信息
- 【MySQL】CentOS7中使用systemctl工具管理启动和停止MySQL
- Pandas应用案例-股票分析:使用tushare包获取股票的历史行情数据进行数据分析
- AmoebaNet:经费在燃烧,谷歌提出基于aging evolution的神经网络搜索 | AAAI 2019
- SAP client锁定
- 百度文库Word下载器
- MySQL调优之分区表
- B-tree R-tree B+-tree indexes 索引顺序存取方法 ISAM MySQL实现拓展ISAM为MyISAM
- Linux监控内核SNMP计数器