题意：这是bc round 71 div 1 的 1004 直接去看中文题意
分析：
首先，一种合法方案对应了原图的一棵生成树。
我们知道，最小生成树有一个性质是最大边最小。
因此，我们可以枚举生成树的最小边，去掉比该边小的边后对新图求最小生成树，那么我们所要的最优解一定包含在其中。
时间复杂度O(Mlog M+M^2*a (N)，显然仅仅这个效率是不够的。
可以发现我们每次枚举后都重新求了最小生成树，事实上这是不必要的。
考虑从大到小枚举生成树的最小边，我们要做的实际上是每次加入一条边，维护当前图的最小生成树。
加入一条边时，我们需要判断这条边能否与之前的边构成环。
I 若能构成环，用该边替代环中最大边一定更优；
II 若不能构成环，直接加入该边即可。
找环中最大边可以用DFS 实现。若图中现有的边数为N-1N−1，我们就可以更新答案。
这样，事件复杂度就降到了O(Mlog M+MN)O(MlogM+MN)。
更高的效率的方法，我们涉及的操作为加边、删边、查询路径最大边，因此可以使用LCT 来维护。
注：我按照题解写了一发，肯定是我手残，没有理解人家的意思，我发现我写出来还没题解上的效率不行的快
肯定我不行，
#include<iostream> #include<stdio.h> #include<string.h> #include<vector> #include<queue> #include<algorithm> using namespace std; typedef long long LL; const int maxn=2002; const int mod=1e9+7; const LL INF=INT_MAX; int head[maxn],p; struct Edge { LL u,v,next; LL w,mark; bool operator<(const Edge &e)const { return w<e.w; } } edge[30005],o[15005]; void add(int u,int v,int w) { edge[p].u=u; edge[p].v=v; edge[p].w=w; edge[p].mark=0; edge[p].next=head[u]; head[u]=p++; } int fa[maxn]; int find(int x) { if(x==fa[x])return x; return fa[x]=find(fa[x]); } LL tmp,vv,_max; void dfs(int u,int f,int res) { if(u==vv) tmp=res; for(int i=head[u]; ~i; i=edge[i].next) { if(edge[i].v==f)continue; if(edge[i].mark)continue; _max=max(_max,edge[i].w); int c=res; if(res==-1||edge[i].w>edge[c].w)c=i; dfs(edge[i].v,u,c); } } int main() { int T,n,m; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i=1; i<=m; ++i) scanf("%I64d%I64d%I64d",&o[i].u,&o[i].v,&o[i].w); sort(o+1,o+1+m); for(int i=1; i<=n; ++i)fa[i]=i; p=0; memset(head,-1,sizeof(head)); int cnt=0; LL ans=INF; for(int i=m; i>0; --i) { tmp=-1,_max=0,vv=o[i].v; if(cnt==n-1) { dfs(o[i].u,0,-1); ans=min(ans,_max-o[i+1].w); } int fx=find(o[i].u); int fy=find(o[i].v); if(fx!=fy) { ++cnt; fa[fx]=fy; } else { if(tmp==-1) dfs(o[i].u,0,-1); edge[tmp].mark=edge[tmp^1].mark=1; } add(o[i].u,o[i].v,o[i].w); add(o[i].v,o[i].u,o[i].w); } if(cnt==n-1) { _max=0; dfs(1,0,-1); ans=min(ans,_max-o[1].w); } if(ans==INF)printf("-1 "); else printf("%I64d ",ans); } return 0; }