给出一个无向图，问在其中任意加入一条边后，删去最小的一条边使得图不连通，这条被删去的边权的最大值
先缩环，因为环上的边不能砍 剩下的边按边权从小到大排序 从最小的边开始每条边考虑，如果他和之前边的并集在一条链上，那么一定有一种加边方案使得他们都在环上，这时他们都不能砍，所以ans一定不比他小 直到有一条边，和之前的边的并集不在一条链上，加入一条边一定不能使他们都在环上，这条边的边权即答案
缩环后，把这些边并起来，LCA讨论一下
code：
#include<set> #include<map> #include<deque> #include<queue> #include<stack> #include<cmath> #include<ctime> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstdlib> #include<cstring> #include<climits> #include<complex> #include<iostream> #include<algorithm> #define ll long long using namespace std; inline void read(int &x) { char c; while(!((c=getchar())>='0'&&c<='9')); x=c-'0'; while((c=getchar())>='0'&&c<='9') (x*=10)+=c-'0'; } inline void up(int &x,const int y){if(x<y)x=y;} inline void down(int &x,const int y){if(x>y)x=y;} inline void swap(int &x,int &y){x^=y;y^=x;x^=y;} const int maxn = 510000; const int maxm = 1100000; const int maxd = 22; int n,m; struct edge { int y,c,nex; edge(){} edge(const int _y,const int _c,const int _nex){y=_y;c=_c;nex=_nex;} }a[maxm<<1]; int len,fir[maxn]; inline void ins(const int x,const int y,const int c){a[++len]=edge(y,c,fir[x]);fir[x]=len;} struct node{int x,y,c;}e[maxm]; inline bool cmp(const node x,const node y){return x.c<y.c;} int t[maxn],tp; bool v[maxn]; int id,dfn[maxn],low[maxn]; int cnt,bel[maxn]; void tarjan(const int x,const int pre) { dfn[x]=low[x]=++id; t[++tp]=x; v[x]=true; for(int k=fir[x];k;k=a[k].nex)if((k^1)!=pre) { const int y=a[k].y; if(!dfn[y]) tarjan(y,k),down(low[x],low[y]); else if(v[y]) down(low[x],dfn[y]); } if(low[x]==dfn[x]) { int la=0; cnt++; while(la!=x) { bel[la=t[tp--]]=cnt; v[la]=false; } } } int dep[maxn],fa[maxn][maxd]; void build_(const int x,const int ff) { for(int i=1;i<maxd;i++) if(fa[x][i-1]) fa[x][i]=fa[fa[x][i-1]][i-1]; for(int k=fir[x];k;k=a[k].nex) if(a[k].y!=ff) { const int y=a[k].y; fa[y][0]=x; dep[y]=dep[x]+1; build_(y,x); } } int LCA(int x,int y) { if(dep[x]<dep[y]) swap(x,y); for(int i=maxd-1;i>=0;i--) if(dep[x]-dep[y]>=(1<<i)) x=fa[x][i]; if(x==y) return x; for(int i=maxd-1;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0]; } int main() { len=1; read(n); read(m); if((ll)n*(n-1)/2==m+1) { printf("-1\n"); return 0; } for(int i=1;i<=m;i++) { int x,y,c; read(x); read(y); read(c); e[i].x=x; e[i].y=y; e[i].c=c; ins(x,y,c); ins(y,x,c); } id=tp=0; tarjan(1,0); if(cnt==1) { printf("-1\n"); return 0; } len=0; memset(fir,0,sizeof fir); for(int i=1;i<=m;i++) { e[i].x=bel[e[i].x]; e[i].y=bel[e[i].y]; if(e[i].x!=e[i].y) ins(e[i].x,e[i].y,e[i].c),ins(e[i].y,e[i].x,e[i].c); } dep[1]=1; build_(1,0); sort(e+1,e+m+1,cmp); int ans=-1; int x=0,y=0,lca=0; for(int i=1;i<=m;i++) if(e[i].x!=e[i].y) { if(dep[e[i].x]>dep[e[i].y]) swap(e[i].x,e[i].y); ans=e[i].c; if(!x) { x=e[i].x,y=e[i].y,lca=x; continue; } if(lca!=x) { int t1=LCA(lca,e[i].y); if(t1==e[i].y||t1!=lca) break; int t2=LCA(e[i].y,x); if(t2==x||t2==e[i].y) { if(dep[x]<dep[e[i].y])x=e[i].y; continue; } if(t2!=lca) break; int t3=LCA(e[i].y,y); if(t3==y||t3==e[i].y) { if(dep[y]<dep[e[i].y])y=e[i].y; continue; } break; } else { int tlca=LCA(e[i].y,y); if(dep[tlca]<=min(dep[x],dep[e[i].x])) { x=e[i].y; lca=tlca; } else if(tlca==y||tlca==e[i].y) { if(dep[x]>dep[e[i].x]) x=e[i].x; if(dep[y]<dep[e[i].y]) y=e[i].y; lca=x; } else break; } } printf("%d\n",ans); return 0; }