读入一个完全图，你要把所有的点分成两个集合(A,B)，使得(max_{u,vin A} d_{u,v}+max_{u,vin B} d_{u,v})最小。
(d)表示边。
(nle 200)
钦定(A)的贡献小于等于(B)。有个暴力的做法：枚举(B)的贡献，然后二分(A)的贡献，得到一系列限制：要求两个点不能再同个集合，或要求两个点不能同时在(A)集。这个东西可以two-sat解决。然后时间复杂度是(O(n^4lg n))。
考虑优化：考虑大于(B)的贡献的边形成的图，这必须要是个二分图；如果某个时候出现了奇环，就可以不用计算了；当有新边加入这个图时，如果边连着的两个点之前已经确定了不在同个集合中（也就是不在同个二分图连通块中），那也不需要计算。要计算的时候只有两个连通块合并的时候，那么只需要计算(O(n))次。于是总时间复杂度为(O(n^3lg n))。
应该还可以优化成(O(n^3))。不过我没写。
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 205
#define INF 1000000000
int n,m;
struct edge{int u,v,w;} ed[N*N];
bool cmpe(edge a,edge b){return a.w<b.w;}
struct EDGE{
int to;
EDGE *las;
};
struct Graph{
EDGE e[N*N*2];
int ne;
EDGE *last[N*2];
void link(int u,int v){
e[ne]={v,last[u]};
last[u]=e+ne++;
}
void clear(){
ne=0;
memset(last,0,sizeof(EDGE*)*(2*n+1));
}
} G;
int dsu[N],xo[N];
void getdsu(int x){
if (dsu[x]==x) return;
getdsu(dsu[x]);
xo[x]^=xo[dsu[x]];
dsu[x]=dsu[dsu[x]];
}
int dfn[N*2],low[N*2],nowdfn;
int st[N*2],tp;
bool ins[N*2];
int col[N*2],nc;
void tarjan(int x){
dfn[x]=low[x]=++nowdfn;
st[++tp]=x;
ins[x]=1;
for (EDGE *ei=G.last[x];ei;ei=ei->las)
if (!dfn[ei->to])
tarjan(ei->to),low[x]=min(low[x],low[ei->to]);
else if (ins[ei->to])
low[x]=min(low[x],dfn[ei->to]);
if (dfn[x]==low[x]){
++nc;
while (st[tp]!=x){
ins[st[tp]]=0;
col[st[tp--]]=nc;
}
ins[x]=0;
col[x]=nc;
tp--;
}
}
bool judge(int da,int db){
G.clear();
for (int i=m;i>db;--i){
int u=ed[i].u,v=ed[i].v;
G.link(u+n,v),G.link(u,v+n);
G.link(v+n,u),G.link(v,u+n);
}
for (int i=db;i>da;--i){
int u=ed[i].u,v=ed[i].v;
G.link(u+n,v);
G.link(v+n,u);
}
memset(dfn,0,sizeof(int)*(n*2+1));
nc=0;
for (int i=1;i<=n*2;++i)
if (!dfn[i])
tarjan(i);
for (int i=1;i<=n;++i)
if (col[i]==col[i+n])
return 0;
return 1;
}
int ans;
void work(int lim){
int l=0,r=lim,res=INF;
while (l<=r){
int mid=l+r>>1;
if (judge(mid,lim)){
res=ed[mid].w;
r=mid-1;
}
else
l=mid+1;
}
ans=min(ans,res+ed[lim].w);
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%d",&n);
if (n==1){
printf("0
");
return 0;
}
for (int i=1;i<=n;++i){
for (int j=i+1;j<=n;++j){
int w;
scanf("%d",&w);
ed[++m]={i,j,w};
}
}
for (int i=1;i<=n;++i)
dsu[i]=i,xo[i]=0;
sort(ed+1,ed+m+1,cmpe);
ans=ed[m].w;
int i;
for (i=m;i>=1;--i){
int u=ed[i].u,v=ed[i].v;
getdsu(u),getdsu(v);
if (dsu[u]!=dsu[v]){
work(i);
xo[dsu[u]]=xo[u]^1^xo[v];
dsu[dsu[u]]=dsu[v];
}
else{
if (xo[u]==xo[v]){
work(i);
break;
}
}
}
if (i==0)
work(0);
printf("%d
",ans);
return 0;
}