题目：
并查集+贪心，从大到小排序，将二人分在不同房间，找到第一个不满足的即为答案。
代码如下：
#include#include #include using namespace std;int n,m,fa[20005],ans,ct,d[20005];struct N{ int hd,to,w;}edge[100005];bool cmp(N x,N y){ return x.w>y.w;}int find(int x){ if(fa[x]==x)return x; else { int root=find(fa[x]); d[x]+=d[fa[x]]; fa[x]=root; } return fa[x];}int main(){ scanf("%d%d",&n,&m); int a,b,c; for(int i=1;i<=m;i++) { ct++; scanf("%d%d%d",&edge[ct].hd,&edge[ct].to,&edge[ct].w); } sort(edge+1,edge+m+1,cmp); for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=m;i++) { int u=find(edge[i].hd); int v=find(edge[i].to); if(u==v&&(d[edge[i].to]-d[edge[i].hd])%2==0)//在同间 { ans=edge[i].w; break; } if(u!=v) { fa[u]=v; d[u]=d[edge[i].to]-d[edge[i].hd]+1;//dhd+du=dto+1; } } printf("%d",ans); return 0;}