AcWing 257.关押犯罪
首先为了方便查看才写成这种分成一个一个的函数的代码,该题解可以去查看这个,与此题解的代码基本一致。
AC代码
时间复杂度 $O(m\cdot\log n)$
/*
* Author : RealKing
* GitHub : https://github.com/Real-king-Ph
* Bolgs : https://blog.csdn.net/RealKing_sblog?spm=1000.2115.3001.5343
* Email : 1604028491@qq.com
*/
#include<iostream>
#include<cstring>
#include<ctime>
using namespace std;
//#define LOCAL
const int N = 1e5+10;
struct M{
int a,b,c;
}criminals[N];
int n , m;
int fa[N] , ck[N]; // 并查集 , 检验的数组
void input(); // 输入
bool check(int a); // 检验是否成立
void init(); // 初始化
int find(int x); // 并查集
void solve(); // 主要函数
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
solve();
#ifdef LOCAL
cout<<"用时"<<(double)clock()/CLOCKS_PER_SEC<<"s"<<endl;
#endif
return 0;
}
void solve(){
input();
int l = 0 , r = 1e9 + 1;
while(l < r){
int mid = l + r >> 1 ; // 二分向上取整
init(); // 初始化
if(check(mid)) r = mid ;
else l = mid + 1 ;
}
printf("%d\n",l);
}
bool check(int a){
for(int i = 1 ; i <= m ; i ++ ){
if(criminals[i].c > a){
int x = find(criminals[i].a) , y = find(criminals[i].b);
if(x == y){
if(ck[criminals[i].a] ^ ck[criminals[i].b] == 0) return false;
}
else{
fa[x] = y;
ck[x] = ck[criminals[i].a] ^ ck[criminals[i].b] ^ 1;
}
}
}
return true;
}
int find(int x){
if(fa[x] == x) return x;
int tmp = find(fa[x]);
ck[x] ^= ck[fa[x]];
return fa[x] = tmp;
}
void init(){
memset(ck,0,sizeof(ck));
for(int i = 1 ; i <= n ; i ++ ) fa[i] = i;
}
void input(){
scanf("%d%d",&n,&m);
for(register int i = 1 ; i <= m ; i ++ ){
int a, b ,c ; scanf("%d%d%d",&a,&b,&c);
criminals[i] = {a,b,c};
}
}
思路
由该题我们可以获得如下的信息
1. 罪犯怒气值越高越要分开
2. 我们只可以知道哪些罪犯不可以在一起住
[HTML_REMOVED][HTML_REMOVED]由 1 我们可以知道该题具有单调性,再加上这个题目每一种情况只能单独算一遍,那么不妨采用二分的方法来进行计算,由 2 我们可以得到如下关系
[HTML_REMOVED][HTML_REMOVED]如果 a 和 b 不能再同一间监狱,且 b 和 c 不能再同一间监狱,那么我们同样也可以得到,a 和 c是可以再同一个监狱的,假设由两个监狱,我们先把不能放在一起的人安置下来,a 在一号监狱,标记为 0 ,b 在二号监狱标记为 1 ,那么 c 不能在二号监狱了,只能在一号监狱,标记为 0 . 如果出现了两个不能再在一起的人,那么这种情况下,即是不行的情况,反之则成立。
[HTML_REMOVED][HTML_REMOVED]假如我们得到的几对关系是分开的关系,那么我们并不需要刻意知道哪个人必须要放在哪个监狱,毕竟,小于最大值的冲突是不重要的。
[HTML_REMOVED]
[HTML_REMOVED]
[HTML_REMOVED]
一、首先写下二分的思路
void solve(){
input();
int l = 0 , r = 1e9 + 1;
while(l < r){
int mid = l + r >> 1 ; // 二分向上取整
init(); // 初始化
if(check(mid)) r = mid ;
else l = mid + 1 ;
}
printf("%d\n",l);
}
二、并查集的写法
由于并查集可以很好的分组,那么我们将几对不可以放在一组的人放在一块,第一个出现的标记为 0 第二个标记为 1 以此类推。
那么可以放在一起的人我们可以标记为 1 1 或者 0 0 不可以则是 0 1 或 1 0
那么我们的并查集可以呈现出如下的形式
那么如果我们出现了第二个并查集该怎么合并呢
假如我们合并的是 5 和 4 那么我们只要将 5 中的 1 改成 0 即可 如果我们要用到六号的时候,我们在将六号修改为 1 既可。那么我们的并查集寻根函数可以写成如下的形式
int find(int x){
if(fa[x] == x) return x;
int tmp = find(fa[x]);
ck[x] ^= ck[fa[x]];
return fa[x] = tmp;
}
下面的就不是很重要了。