传送门
题解： 我们枚举最大边，然后再二分第二大边即可。 注意到加入最大边后如果和不能选的比他大的边形成了偶环，那么一定有一个之前的出现过，我们可以跳过对他的判断。 如果是奇环就一定会出现一条，这时后面的都不用判断了。 时间复杂度 O(n3logn) O ( n 3 log n ) 。
#include <bits/stdc++.h> using namespace std; typedef pair <int,int> pii; const int RLEN=1<<18|1; inline char nc() { static char ibuf[RLEN],*ib,*ob; (ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin)); return (ib==ob) ? -1 : *ib++; } inline int rd() { char ch=nc(); int i=0,f=1; while(!isdigit(ch)) {if(ch=='-')f=-1; ch=nc();} while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=nc();} return i*f; } const int N=4e2+50; int n,m,anc[N],val[N],ans=0x3f3f3f3f; struct E { int x,y,w; E() {} E(int x,int y,int w) : x(x), y(y), w(w) {} friend inline bool operator <(const E &a,const E &b) {return a.w<b.w;} } e[N*N]; inline pii ga(int x) { if(x==anc[x]) return pii(x,0); pii f=ga(anc[x]); val[x]=val[x]^f.second; anc[x]=f.first; return pii(anc[x],val[x]); } map <int,int> S; vector <int> edge[N]; int dfn[N],bl[N],st[N],low[N],ins[N],top,ind,scc; inline void dfs(int x) { dfn[x]=low[x]=++ind; ins[st[++top]=x]=1; for(int e=edge[x].size()-1;e>=0;e--) { int v=edge[x][e]; if(!dfn[v]) dfs(v), low[x]=min(low[x],low[v]); else if(ins[v]) low[x]=min(low[x],dfn[v]); } if(low[x]==dfn[x]) { ++scc; int u; do { u=st[top--]; ins[u]=0; bl[u]=scc; } while(u!=x); } } inline bool check(int lim1,int lim2) { for(int i=1;i<=2*n;i++) edge[i].clear(); memset(dfn,0,sizeof(dfn)); ind=scc=0; for(int i=1;i<=m;i++) { if(e[i].w>lim1) { edge[e[i].x*2-1].push_back(e[i].y*2); edge[e[i].y*2-1].push_back(e[i].x*2); } if(e[i].w>lim2) { edge[e[i].x*2].push_back(e[i].y*2-1); edge[e[i].y*2].push_back(e[i].x*2-1); } } for(int i=1;i<=2*n;i++) if(!dfn[i]) dfs(i); for(int i=1;i<=n;i++) if(bl[i*2]==bl[i*2-1]) return false; return true; } inline void calc(int A) { if(S[A]) return; S[A]=1; int l=0,r=A; while(l<=r) { int mid=(l+r)>>1; if(check(A,mid)) {ans=min(ans,mid+A); r=mid-1;} else l=mid+1; } } int main() { n=rd(); for(int i=1;i<=n;i++) anc[i]=i; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) e[++m]=E(i,j,rd()); sort(e+1,e+m+1); for(int i=m;i>=1;i--) { int x=e[i].x, y=e[i].y; pii xx=ga(x), yy=ga(y); if(xx.first==yy.first) { if(xx.second!=yy.second) continue; else {calc(e[i].w); break;} } calc(e[i].w); anc[xx.first]=yy.first; val[xx.first]=xx.second^yy.second^1; } calc(0); cout<<ans<<'\n'; }