P1525 关押罪犯
题意
略(中文)
思路
扩展域并查集(当然二分图也可以做),开二倍数组,(1,n)记录关在同一个监狱里,(n+1,2*n)记录与自己不同监狱的,因为还有怨气值,所以怨气值要从大到小排序,保证怨气值大的不在一块,这样就能使怨气值最大的最小,然后依次判断就行了.
代码
#include<bits/stdc++.h>
using namespace std
;
const int maxn
=1e5+10;
struct node
{
int x
,y
,c
;
bool operator < (const node
& b
) const {
return c
>b
.c
;
}
}a
[maxn
];
int fa
[maxn
];
int find(int x
){
if(x
==fa
[x
]) return x
;
else return fa
[x
]=find(fa
[x
]);
}
int main(){
int n
,m
;scanf("%d%d",&n
,&m
);
for(int i
=1;i
<=m
;i
++)
scanf("%d%d%d",&a
[i
].x
,&a
[i
].y
,&a
[i
].c
);
sort(a
+1,a
+m
+1);
for(int i
=1;i
<=2*n
;i
++) fa
[i
]=i
;
int ans
=0;
for(int i
=1;i
<=m
;i
++){
int x
=find(a
[i
].x
),y
=find(a
[i
].y
);
int fx
=find(a
[i
].x
+n
),fy
=find(a
[i
].y
+n
);
if(x
==y
){
ans
=a
[i
].c
;
break;
}
fa
[x
]=fy
,fa
[y
]=fx
;
}
printf("%d\n",ans
);
}
