传送门：QAQQAQ
题意：noip2011就要来了，W校的同学们不仅看重这次比赛，更看重noip2011和谁住在同一个房间。同学之间的关系好坏可以用一个亲密值表示，亲密值越大，两个同学关系越好。小A作为W校信息组的组长，自然想要让同学们在比赛前能好好休息，放松心情，让同学们在赛场上能够超常发挥。他现在知道自己预订的房间都是双人间，且知道这n个同学之间的关系。n个同学的关系可以用一个n条双向边的连通图来描述，即某个同学只愿意和与他有边相连的同学住同一个房间，边权即为两个同学的亲密值。数据保证没有重边、自环。现在小A想知道在让所有同学的要求满足的情况下，亲密值最低的一对同学亲密值最高是多少。
思路：比赛的时候居然没想出来，打了个暴力只有30分。。。（这场比赛打炸了说）
这道题第一反应是二分，事实上只要$O(n)$贪心即可。
因为有$n$个点$n$条边，而且是个连通图，所以它是一个基环树（只有一个环），我们考虑只是一个树的情况：枚举每一个叶子结点，然后因为它们的度为1，所以只能和它们的父亲相连，然后和拓扑排序一样删边，遇到有点不能匹配或者有点匹配两次，就$No Answer$
我们就这样“拓扑排序”，剩下来没有搜到的点一定在一个环里而且这个环没有被破坏（这里需要人工YY一下），那么我们就可以对这个环进行染色，然后分两种情况求最小值即可。
代码：（强调！vector的size一定要转为int！）
#include<bits/stdc++.h> using namespace std; const int N=200001; const int inf=(int)2e9; struct Edge{ int to,w; Edge(){} Edge(int to,int w) : to(to),w(w){} }; vector<Edge> E[N]; vector<Edge> R; int F; int n,ans=inf; int f,vis[N]; int deg[N],bl[N]; queue<int> q; void dfs(int u,int f) { vis[u]=1; for(int i=0;i<(int)E[u].size();i++) { int v=E[u][i].to; if(v==f||bl[v]) continue; R.push_back(E[u][i]); if(!vis[v]) dfs(v,u); break; } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { int x,y,W; scanf("%d%d%d",&x,&y,&W); E[x].push_back(Edge(y,W)); E[y].push_back(Edge(x,W)); deg[x]++; deg[y]++; } for(int i=1;i<=n;i++) if(deg[i]==1) q.push(i); int sum=0; while(!q.empty()) { int u=q.front(),v=-1; q.pop(); if(bl[u]) continue; bl[u]=1; for(int i=0;i<E[u].size();i++) { int now=E[u][i].to;//之前直接赋值为v,就算不成立下面也不会判 if(bl[now]) continue; v=now; ans=min(ans,E[u][i].w); break; } if(v==-1) { puts("no answer"); return 0; } bl[v]=1; sum+=2; for(int i=0;i<(int)E[v].size();i++) { int p=E[v][i].to; if(bl[p]) continue; deg[p]--; if(deg[p]==1) q.push(p); } } if(sum==n) { cout<<ans<<endl; return 0; } for(int i=1;i<=n;i++) if(!bl[i]) F=i; dfs(F,-1); if((int)R.size()%2==1) { puts("no answer"); return 0; } int now1=inf,now2=inf; for(int i=0;i<(int)R.size();i++) { if(i%2==0) now1=min(now1,R[i].w);//之前min写成加了 else now2=min(now2,R[i].w); } ans=min(ans,max(now1,now2)); cout<<ans<<endl; return 0; }