- 题目链接：关押罪犯
- 题目思路：根据题意，这道题很明显要用并查集，用种类并查集来模拟两个监狱，根据怒气值降序排序，尽量将怒气大的罪犯分开，具体解释见代码。
- 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
using namespace std;
int sc() {
int xx=0,ff=1; char cch=gc;
while(cch<'0'|| cch>'9') {
if(cch=='-') ff=-1; cch=gc;
}
while(cch>='0'&& cch<='9') {
xx=(xx<<1)+(xx<<3)+(cch^'0'); cch=gc;
}
return xx*ff;
}
struct node {
int x,y,num;
bool operator < (const node &xx) const {
return num>xx.num;
}
}a[Maxm];
int n,m;
int fa[Maxn<<1];
int find(int x) {
return x==fa[x]? x: fa[x]=find(fa[x]);
}
int main() {
n=sc(); m=sc();
for(int i=1; i<=(n<<1); i++) //初始化并查集时要开双倍空间，每一倍模拟一个监狱
fa[i]=i;
for(int i=1; i<=m; i++) {
a[i].x=sc();
a[i].y=sc();
a[i].num=sc();
}
sort(a+1, a+m+1); //排序
for(int i=1; i<=m+1; i++) { //循环到m+1，因为降序排序，第m+1的值肯定是0
int xx=find(a[i].x);
int yy=find(a[i].y);
if(xx==yy) {
printf("%d\n",a[i].num);
return 0;
}
// fa[fa[a[i].x]]=fa[find(a[i].y+n)];
// fa[fa[a[i].y]]=fa[find(a[i].x+n)];
fa[find(a[i].x)]=fa[find(a[i].y+n)]; //将两人分到两个监狱
fa[find(a[i].y)]=fa[find(a[i].x+n)];
}
return 0;
}