这又是一道坑题！
思想进行了大幅转变，并查集炸了之后终于搞出了一种奇葩的算法，终于卡时间A了。
把思路按顺序理一理。
先把边从大到小排序一下。
<1> 看完题目，我去这不是并查集模板么吗，马上敲了个裸并查集，判断两个点如果之前已经联通了，直接退出输出当前值即可。
CODE（WA）
#include<cstdio> #include<algorithm> using namespace std; const int N=20005,M=100005; struct data { int l,r,s; }e[N]; int father[N],i,n,m; inline void read(int &x) { x=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } inline int comp(data a,data b) { return a.s>b.s; } inline int getfather(int k) { return k==father[k]?k:father[k]=getfather(father[k]); } int main() { read(n); read(m); for (i=1;i<=n;++i) father[i]=i; for (i=1;i<=m;++i) read(e[i].l),read(e[i].r),read(e[i].s); sort(e+1,e+m+1,comp); for (i=1;i<=m;++i) { int fx=getfather(e[i].l),fy=getfather(e[i].r); if (fx==fy) break; father[fx]=fy; } printf("%d",e[i].s); return 0; }
帅气得搞了50分·。
<2> 上一种打法为什么会WA，是因为没有考虑到一种情况：如果两个人之间的距离是偶数，那么他们应该在同一个监狱（类似于我的敌人的敌人就是我的朋友）。类似的思想在食物链这道题里面也有。
然后就是一道带权并查集的模板题了（可是我不会）
不过可以用补集的做法来搞
开两倍的数组，每次连边的时候把x和y+n相连，y和x+n相连。这样如果两个点的父节点相同那么它们之间的距离肯定是偶数。
CODE（TLE）
#include<cstdio> #include<algorithm> using namespace std; const int N=20005,M=100005; struct data { int l,r,s; }e[N]; int father[N*2],i,n,m; inline void read(int &x) { x=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } inline int comp(data a,data b) { return a.s>b.s; } inline int getfather(int k) { return k==father[k]?k:father[k]=getfather(father[k]); } int main() { read(n); read(m); for (i=1;i<=n*2;++i) father[i]=i; for (i=1;i<=m;++i) read(e[i].l),read(e[i].r),read(e[i].s); sort(e+1,e+m+1,comp); for (i=1;i<=m;++i) { int fx=getfather(e[i].l),fy=getfather(e[i].r); if (fx==fy) { printf("%d",e[i].s); return 0; } father[fx]=getfather(e[i].r+n); father[fy]=getfather(e[i].l+n); } puts("0"); return 0; }
然后蜜汁TLE了4个点
<3> 终于，发现了一种神奇的算法。因为已经对边长排过序，并且稍微想一想就可以得出如果到这一条边不能满足要求，那么所有比它小的边绝对也满足不了。
于是——二分。
对于二分出来的边长，只保留比它长的边，再跑一遍染色即可。
所谓染色，就是把一个点染上一种颜色（例如1），再把与它相邻的点染上另一种颜色即可（例如2）。
如果发现一个点与之相连的点颜色和它一样，说明不可行，return 掉即可。
BFS实现玄学复杂度，常数小的应该能卡过去
CODE(AC)
#include<cstdio> #include<vector> #include<algorithm> #include<cstring> using namespace std; const int N=20005,M=100005; vector <int> a[N],l[N]; int n,m,i,j,ans,col[N],q[N*2+10],e[M],x,y; inline void read(int &x) { x=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } inline int comp(int a,int b) { return a>b; } inline bool check(int x) { memset(col,0,sizeof(col)); for (i=1;i<=n;++i) if (!col[i]) { memset(q,0,sizeof(q)); int head=0,tail=1; q[1]=i; col[i]=1; while (head<tail) { int now=q[++head]; for (j=0;j<a[now].size();++j) { int k=a[now][j]; if (l[now][j]>x) { if (!col[k]) { col[k]=3-col[now]; q[++tail]=k; } else if (col[k]==col[now]) return 0; } } } } return 1; } int main() { read(n); read(m); for (i=1;i<=m;++i) { read(x); read(y); read(e[i]); a[x].push_back(y); l[x].push_back(e[i]); a[y].push_back(x); l[y].push_back(e[i]); } sort(e+1,e+m+1,comp); int l=1,r=m+1; while (l<=r) { int mid=l+r>>1; if (check(e[mid])) ans=mid,l=mid+1; else r=mid-1; } printf("%d",e[ans]); return 0; }