先从大到小排序，看到哪个的时候安排不开了
给每个人拆成两个，如果x和y有矛盾，就给x和y‘、y和x’连边；如果a和b（或a'和b'）在同一个集合里，说明他们一定要在同一个监狱里。
1 #include<bits/stdc++.h> 2 #define pa pair<int,int> 3 #define CLR(a,x) memset(a,x,sizeof(a)) 4 using namespace std; 5 typedef long long ll; 6 const int maxn=20020,maxm=100010; 7 8 inline ll rd(){ 9 ll x=0;char c=getchar();int neg=1; 10 while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();} 11 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 12 return x*neg; 13 } 14 15 struct Node{ 16 int a,b,c; 17 }op[maxm]; 18 int N,M,fa[maxn*2]; 19 20 inline bool cmp(Node a,Node b){return a.c>b.c;} 21 22 inline int getf(int x){return fa[x]==x?x:fa[x]=getf(fa[x]);} 23 inline void add(int a,int b){ 24 fa[getf(a)]=getf(b); 25 } 26 27 int main(){ 28 //freopen("","r",stdin); 29 int i,j,k; 30 N=rd(),M=rd(); 31 for(i=1;i<=M;i++){ 32 op[i].a=rd(),op[i].b=rd(),op[i].c=rd(); 33 }sort(op+1,op+M+1,cmp); 34 for(i=1;i<=N*2;i++) fa[i]=i; 35 for(i=1;i<=M;i++){ 36 if(getf(op[i].a)!=getf(op[i].b)){ 37 add(op[i].a,op[i].b+N); 38 add(op[i].a+N,op[i].b); 39 }else{ 40 printf("%d ",op[i].c); 41 return 0; 42 } 43 }printf("0 "); 44 return 0; 45 }