题面甚至没给范围，由数据可得n<=200。容易想到二分答案，暴力枚举某集合的价值，2-SATcheck一下即可。这样是O(n⁴logn)的。

　　2-SAT复杂度已经是下界，考虑如何优化枚举。稍微改一下，不妨从大到小枚举较大的集合价值（即枚举边），另一个集合二分答案，同样O(n⁴logn)。

　　看起来没什么卵用。但注意到较大集合所不能包含的边不可以成奇环，否则肯定有一条环上边被选中。那么考虑当前边，如果形成奇环，最大值不可能比它更小了，做完这个就可以退出；如果加上这条边后形成偶环，可以直接跳过，因为如果要让其被选中，相当于将偶环缩成了奇环，剩余边肯定有一条被选中而又比它大。不形成环时则直接做。由于树边数量O(n)，复杂度O(n³logn)。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long#define N 210#define inf 1000000010int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,a[N][N],b[N*N],dfn[N<<1],low[N<<1],stk[N<<1],belong[N<<1],p[N<<1],fa[N<<1],deep[N<<1],size[N<<1],len[N<<1],t,top,tot,cnt,ans=inf,m;bool flag[N<<1];struct data{ int to,nxt;}edge[N*N<<3];struct data2{ int x,y,z; bool operator <(const data2&a) const { return z
           
            x) addedge(i*2-1,j*2),addedge(j*2-1,i*2); if (a[i][j]>y) addedge(i*2,j*2-1),addedge(j*2,i*2-1); } for (int i=1;i<=n*2;i++) if (!dfn[i]) tarjan(i); for (int i=1;i<=n;i++) if (belong[i*2-1]==belong[i*2]) return 0; return 1;}int find(int x){ if (fa[x]==x) return x; int f=find(fa[x]); deep[x]=deep[fa[x]]^len[x]; return f;}int main(){#ifndef ONLINE_JUDGE freopen("bzoj4078.in","r",stdin); freopen("bzoj4078.out","w",stdout); const char LL[]="%I64d\n";#else const char LL[]="%lld\n";#endif n=read(); for (int i=1;i
            
             =1;i--) { int p=find(e[i].x),q=find(e[i].y); if (size[p]
             
              >1; if (check(e[i].z,e[mid].z)) u=e[mid].z,r=mid-1; else l=mid+1; } ans=min(ans,e[i].z+u); } if (p==q&&(deep[e[i].x]^deep[e[i].y]^1)) break; } if (ans==inf) ans=0;cout<