Description
Input
Output
Sample Input
Sample Output
Hint
Solution
非常显然的并查集题目，在本题中，对于每个罪犯i，维护两个信息：必须要和他关在一起的罪犯的集合，以及和他有仇的罪犯的集合，由于*只有两个，所以和他有仇的罪犯一定被关在同一个集合里面。sort一遍贪心从上到下扫描。对于不得不管起来的两个有仇的人即为答案。
Code
#include<cstdio>
#include<algorithm>
namespace read{
void imop(int&x){
char ch=getchar();
while(ch<''||ch>'') ch=getchar();
while(ch>=''&&ch<='') x=x*+ch-'', ch=getchar();
return;
}
void op(int&x){
char ch=getchar();
int f=;
while(ch<''||ch>''){
if(ch=='-') f=-;
ch=getchar();
}
while(ch>=''&&ch<='') x=x*+ch-'', ch=getchar();
x*=f;
return;
}
}
namespace fusu{
const int maxn = , maxm = ;
struct Crim{
int a,b,value;
};
Crim criminal[maxm];
int n,m;
inline bool cmp(Crim a,Crim b){return a.value<b.value;}
int frog[maxn],enemy[maxn];
inline int find(int x){
if(frog[x]^x) frog[x]=find(frog[x]);
return frog[x];
}
void gather(int a,int b){
int fa=find(frog[a]),fb=find(frog[b]);
frog[fa]=fb;
return;
}
void beginning(){
for(int i=;i<=n;++i)
frog[i]=i;
return;
}
int doit(){
read::imop(n);read::imop(m);
for(int i=;i<=m;++i){
read::imop(criminal[i].a);
read::imop(criminal[i].b);
read::imop(criminal[i].value);
}
std::sort(criminal+,criminal++m,cmp);
beginning();
do{
int fa=find(frog[criminal[m].a]),fb=find(frog[criminal[m].b]);
if(!(fa^fb)){
printf("%d\n",criminal[m].value);
return ;
}
if(!enemy[criminal[m].a]) enemy[criminal[m].a]=criminal[m].b;
else gather(enemy[criminal[m].a],criminal[m].b);
if(!enemy[criminal[m].b]) enemy[criminal[m].b]=criminal[m].a;
else gather(enemy[criminal[m].b],criminal[m].a);
--m;
}while(m);
printf("0\n");
return ;
}
}
int main(){
return fusu::doit();
}
Summary
对于并查集中的补集法，对于每个个体记录多个信息，在合并时合并多个信息即可。