题意：给你m条边，每条边有一个权值，每次询问只保留编号l到r的边，让你把这个图分成两部分
一个方案的耗费是当前符合条件的边的最大权值（符合条件的边指两段点都在一个部分），问你如何分，可以让耗费最小
分析：把当前l到r的边进行排序，从大到小，从大的开始不断加边，判断当前能否形成二分图，如果能形成二分图，继续加边
如果不能形成二分图，那当前边的权值就是最小耗费(是不是很眼熟)
思路很清晰，现在我们要解决的是如何判断可以形成二分图，有两种，一个是2染色当前图（肯定超时）
所以只剩一种方法，带权并查集
带权并查集三步走
1：设计权值数组relation[i],代表i节点和它的根的关系，0代表属于一个部分，1代表不属于一个部分
2：路径压缩，relation[i]=relation[i]^relation[fa[i]]，递归得到和根的关系
3：合并根节点,relation[i]=relation[u]^relation[v]^1;
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <stack> #include <cstring> #include <algorithm> using namespace std; const int N=5e5+5; int fa[N],relation[N]; struct Edge{ int u,v,w,id; bool operator<(const Edge &rhs)const{ return w>rhs.w; } }p[N]; int find(int x){ if(x==fa[x])return x; int fx=find(fa[x]); relation[x]^=relation[fa[x]]; return fa[x]=fx; } bool Union(int u,int v){ int fx=find(u),fy=find(v); if(fx==fy){ if(relation[u]==relation[v]) return false; return true; } fa[fx]=fy; relation[fx]=relation[u]^relation[v]^1; return true; } int main(){ int n,m,q; scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=m;++i){ scanf("%d%d%d",&p[i].u,&p[i].v,&p[i].w); p[i].id=i; } sort(p+1,p+1+m); while(q--){ int l,r,ret=-1; scanf("%d%d",&l,&r); for(int i=1;i<=n;++i)fa[i]=i,relation[i]=0; for(int i=1;i<=m;++i){ if(p[i].id<l||p[i].id>r)continue; if(!Union(p[i].u,p[i].v)){ ret=p[i].w;break;} } printf("%d ",ret); } return 0; }