题目链接

题意：有 \(n\) 个元素，第 \(i\) 个数与第 \(j\) 个数之间有一个权值 \(d_{i,j}\)，\(d(i,j)=d(j,i)\)。

定义函数 \(D(S)=\max\limits_{i \in S,j \in S,i \neq j}d(i,j)\)。

现在你要将 \(n\) 个元素划分为两个集合 \(A,B\)，求 \(\min{D(A)+D(B)}\)。

\(1 \leq n \leq 200\)。

第一道 ACM World Final，祭一个。

看到这种非黑即白的问题，自然可以想到 2-SAT 啦。

很显然的思路是，不妨设 \(D(A)>D(B)\)，枚举 \(D(A)\) 可能的值，二分 \(D(B)\) 的值，用 2-SAT 判定合法性，对于每个 \(d(i,j)>D(A)\)，如果 \(i \in A\)，那么 \(j \notin A\)，\(D(B)\) 也同理。

不过这样是 \(n^4 \log n\) 的，因此需要优化。

我们将每个 \((i,j)\) 看做一条边，边权为 \(d(i,j)\)，那么我们将边权从大到小排序，并顺次加边。

如果加入边权为 \(x\) 的边之后，图出现了奇数环，那么处理完 \(x\) 之后直接退出，因为我们无法对边权 \(\geq x\) 的进行黑白染色，使得同一条边两个端点颜色不同。

同理，如果加入边权为 \(x\) 的边之后，图出现了偶数环，那么这条边一定不能是 \(A\) 中边权最大的边。因为如果它是 \(A\) 中边权最大的边，那么它的两个端点颜色相同，可以看作一个点，偶数环变成了奇数环，显然是不满足条件的。

这样一来，我们最多只会加入 \(n-1\) 条树边，时间复杂度就降到了 \(n^3 \log n\) 了。

坑点：特判 \(n \leq 2\) 答案为 \(0\)，我为此不停地 WA 3，然后发现 test 3 \(n=1\)？

//Coded by tzc_wk
/*
数据不清空，爆零两行泪。
多测不读完，爆零两行泪。
边界不特判，爆零两行泪。
贪心不证明，爆零两行泪。
D P 顺序错，爆零两行泪。
大小少等号，爆零两行泪。
变量不统一，爆零两行泪。
越界不判断，爆零两行泪。
调试不注释，爆零两行泪。
溢出不 l l，爆零两行泪。
*/
#include <bits/stdc++.h>
using namespace std;
#define fi            first
#define se            second
#define fz(i,a,b)    for(int i=a;i<=b;i++)
#define fd(i,a,b)    for(int i=a;i>=b;i--)
#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define all(a)        a.begin(),a.end()
#define giveup(...) return printf(__VA_ARGS__),0;
#define fill0(a)    memset(a,0,sizeof(a))
#define fill1(a)    memset(a,-1,sizeof(a))
#define fillbig(a)    memset(a,0x3f,sizeof(a))
#define fillsmall(a) memset(a,0xcf,sizeof(a))
#define mask(a)        (1ll<<(a))
#define maskx(a,x)    ((a)<<(x))
#define _bit(a,x)    (((a)>>(x))&1)
#define _sz(a)        ((int)(a).size())
#define filei(a)    freopen(a,"r",stdin);
#define fileo(a)    freopen(a,"w",stdout);
#define fileio(a)     freopen(a".in","r",stdin);freopen(a".out","w",stdout)
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define put(x)        putchar(x)
#define eoln        put('\n')
#define space        put(' ')
#define y1            y_chenxiaoyan_1
#define y0            y_chenxiaoyan_0
#define int long long
typedef pair<int,int> pii;
inline int read(){
    int x=0,neg=1;char c=getchar();
    while(!isdigit(c)){
        if(c=='-')  neg=-1;
        c=getchar();
    }
    while(isdigit(c))   x=x*10+c-'0',c=getchar();
    return x*neg;
}
inline void print(int x){
    if(x<0){
        putchar('-');
        print(abs(x));
        return;
    }
    if(x<=9)    putchar(x+'0');
    else{
        print(x/10);
        putchar(x%10+'0');
    }
}
inline int qpow(int x,int e,int _MOD){
    int ans=1;
    while(e){
        if(e&1) ans=ans*x%_MOD;
        x=x*x%_MOD;
        e>>=1;
    }
    return ans;
}
struct edge{
    int u,v,w;
    edge(){/*ycxakioi*/}
    edge(int _u,int _v,int _w){
        u=_u;v=_v;w=_w;
    }
    friend bool operator <(edge a,edge b){
        return a.w<b.w;
    }
} e[40005];
int n=read(),cnt=0;
int f[405],col[405],siz[405];
inline int find(int x){
    return (f[x]==x)?x:find(f[x]);
}
inline int getc(int x){
    return (f[x]==x)?0:(getc(f[x])^col[x]);
}
vector<int> g[405];
int dfn[405],idx=0,low[405],stk[405],top,comp,bel[405],vis[405];
inline void tarjan(int x){
    dfn[x]=low[x]=++idx;stk[++top]=x;vis[x]=1;
    foreach(it,g[x]){
        int y=*it;
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(vis[y]){
            low[x]=min(low[x],dfn[y]);
        }
    }
    if(low[x]==dfn[x]){
        comp++;
        while(top){
            int y=stk[top--];
            vis[y]=0;
            bel[y]=comp;
            if(y==x)    break;
        }
    }
}
inline bool _2_SAT(int mn1,int mn2){
    fill0(dfn);fill0(low);fill0(stk);fill0(vis);fill0(bel);
    comp=top=idx=0;
    fz(i,0,404) g[i].clear();
    fz(i,1,cnt){
        if(e[i].w>mn1)  g[e[i].u*2-1].push_back(e[i].v*2),g[e[i].v*2-1].push_back(e[i].u*2);
        if(e[i].w>mn2)  g[e[i].u*2].push_back(e[i].v*2-1),g[e[i].v*2].push_back(e[i].u*2-1);
    }
    fz(i,1,n*2) if(!dfn[i]) tarjan(i);
    fz(i,1,n)   if(bel[i*2-1]==bel[i*2])    return 0;
    return 1;
}
signed main(){
    fz(i,1,n)   fz(j,i+1,n){
        int t=read();
        e[++cnt].u=i;
        e[cnt].v=j;
        e[cnt].w=t;
    }
    if(n<=2)    return puts("0"),0;
    sort(e+1,e+cnt+1);
    fz(i,1,n*2) f[i]=i,siz[i]=1;
    int ans=INT_MAX;
    fd(i,cnt,1){
        int x=e[i].u,y=e[i].v,z=e[i].w;
        int xx=find(x),yy=find(y);
        if(xx!=yy){
            if(siz[xx]<siz[yy]) swap(x,y),swap(xx,yy);
            if(getc(x)==getc(y))    col[yy]^=1;
            f[yy]=xx;
            siz[xx]+=siz[yy];
        }
        else if(getc(x)!=getc(y))   continue;
        int l=0,r=i-1,anss=0x3f3f3f3f;
        while(l<=r){
            int mid=(l+r)>>1;
            if(_2_SAT(e[i].w,e[mid].w)) anss=e[mid].w,r=mid-1;
            else                        l=mid+1;
        }
        ans=min(ans,e[i].w+anss);
        if(getc(x)==getc(y))    break;
    }
    cout<<ans<<endl;
    return 0;
}