设$D(A)\leq D(B)$，从小到大枚举$D(A)$，双指针从大到小枚举$D(B)$。
那么对于权值不超过$D(A)$的边，可以忽略。
对于权值介于$(D(A),D(B)]$之间的边，需要满足那两个点不能都在集合$A$。
对于权值大于$D(B)$的边，需要满足那两个点不在同一个集合。
所以建图判断2-SAT是否有解即可，这可以使用压位Kosaraju算法。
时间复杂度$O(\frac{n^4}{64})$。
#include<cstdio>
#include<algorithm>
#define N 205
using namespace std;
typedef unsigned long long ll;
int n,m,i,j,k,t,q[N<<1],f[N<<1],ans;
struct E{int x,y,w;E(){}E(int _x,int _y,int _w){x=_x,y=_y,w=_w;}}e[N*N];
inline bool cmp(const E&a,const E&b){return a.w<b.w;}
struct BIT{
ll v[4];
void clear(){for(int i=0;i<4;i++)v[i]=0;}
void flip(int x){v[x>>6]^=1ULL<<(x&63);}
int get(int x){return v[x>>6]>>(x&63)&1;}
}v0,v1,g0[N<<1],g1[N<<1];
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
inline void addA(int x,int y){
g0[x].flip(y);
g1[y+n].flip(x);
g0[y].flip(x);
g1[x+n].flip(y);
}
inline void addB(int x,int y){
g0[x+n].flip(y);
g1[y].flip(x);
g0[y+n].flip(x);
g1[x].flip(y);
}
void dfs1(int x){
if(x<n){
v0.flip(x);
for(int i=0;i<4;i++)while(1){
ll o=v1.v[i]&g0[x].v[i];
if(!o)break;
dfs1((i<<6|__builtin_ctzll(o))+n);
}
}else{
v1.flip(x-n);
for(int i=0;i<4;i++)while(1){
ll o=v0.v[i]&g0[x].v[i];
if(!o)break;
dfs1(i<<6|__builtin_ctzll(o));
}
}
q[++t]=x;
}
void dfs2(int x,int y){
f[x]=y;
if(x<n){
v0.flip(x);
for(int i=0;i<4;i++)while(1){
ll o=v1.v[i]&g1[x].v[i];
if(!o)break;
dfs2((i<<6|__builtin_ctzll(o))+n,y);
}
}else{
v1.flip(x-n);
for(int i=0;i<4;i++)while(1){
ll o=v0.v[i]&g1[x].v[i];
if(!o)break;
dfs2(i<<6|__builtin_ctzll(o),y);
}
}
}
inline bool check(){
int i;
v0.clear(),v1.clear();
for(i=0;i<n;i++)v0.flip(i),v1.flip(i);
for(t=i=0;i<n;i++)if(v0.get(i))dfs1(i);
for(i=0;i<n;i++)if(v1.get(i))dfs1(i+n);
for(i=0;i<n;i++)v0.flip(i),v1.flip(i);
for(i=t;i;i--)if(q[i]<n){if(v0.get(q[i]))dfs2(q[i],q[i]);}else if(v1.get(q[i]-n))dfs2(q[i],q[i]);
for(i=0;i<n;i++)if(f[i]==f[i+n])return 0;
return 1;
}
void solve(){
ans=~0U>>1;
sort(e+1,e+m+1,cmp);
for(i=0;i<n+n;i++)g0[i].clear(),g1[i].clear();
for(i=1;i<=m;i++)addA(e[i].x,e[i].y);
for(i=0,j=m;i<=j;i++){
if(i)addA(e[i].x,e[i].y);
while(e[i].w+e[j].w>=ans||check()){
ans=min(ans,e[i].w+e[j].w);
if(j)addB(e[j].x,e[j].y);
if((--j)<i)return;
}
}
}
int main(){
while(~scanf("%d",&n)){
for(m=i=0;i<n;i++)for(j=i+1;j<n;j++)read(k),e[++m]=E(i,j,k);
solve();
printf("%d\n",ans);
}
return 0;
}