省队成员（大部分）都没来...像我这种沙茶天天写写玄学算法都能排在榜上面...果然正解写挂的人远比暴力拍对的人少啊...陆陆续续会补一些题解。（不过有些题太神了可能补不上题解
有n个物品，两个袋子A和B。若物品i与j放在同一个袋子里，那么代价为T[i][j]，保证T[i][i]=0，T[i][j]=T[j][i]。
一个袋子的代价D=袋子中两两物品代价的最大值。你需要将物品分配到两个袋子中，最小化D(A)+D(B)。
2<=n<=250，0<=T[i][j]<=10^9。
陈旭大爷有一种暴力倍增的做法可以跑过去...跪烂
我们不妨设D(A)<=D(B)，那么我们枚举D(B)，显然可以二分D(A)判可行性。
对于两物品i,j，如果D(A)<T[i][j]<=D(B)，那么i和j至少要有一个在B中。如果T[i][j]>D(b)，那么i和j就不能放在一起。
所以这就成了一个2-sat问题，可以用经典的tarjan做法解决。
这样是O(n^4logn)的，由于过于玄学只能得到部分分。
这个做法看起来已经十分优秀了，要怎么优化呢？
我们发现枚举D(B)看起来就不太靠谱，真的要枚举O(n^2)种取值吗？
显然不要，我们考虑搞出一棵最大生成树，以T为边权。接下来考虑对这棵生成树黑白染色，如果一个集合B包括了两种颜色的点，那么显然D(B)就是最大生成树上的边（可以由kruskal算法的正确性得到）。否则B只包括一种颜色的点，只包含所有白点或只包含所有黑点（为什么是所有点呢？因为如果是部分点，那么A肯定包括另一种颜色的全部点。由于是最大生成树，那么D(A)>D(B)）。所以我们只要尝试这些D(B)即可。
这样似乎就是O(n^3logn)的。
我们可以加一些奇技淫巧来优化，我的做法是将权值离散二分，然后每次根据最优解随便剪剪枝，这样就可以过了。
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define SZ 666
int n,t[SZ][SZ],ls[SZ*SZ],ln=0,en=0;
int ff[SZ];
int gf(int x)
{
return ff[x]?ff[x]=gf(ff[x]):x;
}
int M=0,fst[SZ*SZ*5],vb[SZ*SZ*5],nxt[SZ*SZ*5];
void ad_de(int a,int b) {++M; nxt[M]=fst[a]; fst[a]=M; vb[M]=b;}
void adde(int a,int b) {ad_de(a,b); ad_de(b,a);}
struct edg {int x,y;}es[SZ*SZ];
bool operator < (edg a,edg b) {return t[a.x][a.y]>t[b.x][b.y];}
int ds[SZ*SZ],dn=0;
int col[SZ];
void dfs(int x,int c)
{
if(col[x]!=-1) return;
col[x]=c;
for(int e=fst[x];e;e=nxt[e]) dfs(vb[e],!c);
}
//tarjan
namespace TJ
{
int M=0,fst[SZ*SZ*5],nxt[SZ*SZ*5],vb[SZ*SZ*5];
void ad_de(int a,int b) {++M; nxt[M]=fst[a]; fst[a]=M; vb[M]=b;}
void adde(int a,int b) {ad_de(a,b); ad_de(b,a);}
int ss[SZ],sn=0,low[SZ],dfn[SZ],cnt=0,bl[SZ],scc=0;
bool ins[SZ];
void init()
{
M=sn=cnt=scc=0;
for(int i=1;i<=2*n+1;i++) fst[i]=low[i]=dfn[i]=bl[i]=ins[i]=0;
}
void tarjan(int x)
{
low[x]=dfn[x]=++cnt; ss[++sn]=x; ins[x]=1;
for(int e=fst[x];e;e=nxt[e])
{
int b=vb[e];
if(!dfn[b]) {tarjan(b); low[x]=min(low[x],low[b]);}
else if(ins[b]) low[x]=min(low[x],dfn[b]);
}
if(dfn[x]!=low[x]) return;
int p; ++scc;
do
{
p=ss[sn--]; ins[p]=0; bl[p]=scc;
}while(p!=x);
}
}
bool ok(int da,int db)
{
TJ::init();
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
int T=t[i][j];
if(T>db)
{
TJ::adde(i*2,j*2+1); TJ::adde(i*2+1,j*2);
}
else if(T>da)
{
TJ::ad_de(i*2,j*2+1); TJ::ad_de(j*2,i*2+1);
}
}
}
for(int i=2;i<=2*n+1;i++)
{
if(!TJ::dfn[i]) TJ::tarjan(i);
}
for(int i=1;i<=n;i++) if(TJ::bl[i*2]==TJ::bl[i*2+1]) return 0;
return 1;
}
struct F{F(string t){freopen((t+".in").c_str(),"r",stdin);freopen((t+".out").c_str(),"w",stdout);}}__
("florida");
int main()
{
memset(col,-1,sizeof(col));
M=dn=ln=en=0;
memset(fst,0,sizeof(fst));
memset(ff,0,sizeof(ff));
if(scanf("%d",&n)==EOF) return 0;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++) scanf("%d",&t[i][j]), t[j][i]=t[i][j];
}
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++) if(t[i][j]) ls[++ln]=t[i][j];
}
sort(ls+1,ls+1+ln); ln=unique(ls+1,ls+1+ln)-ls-1;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++) es[++en].x=i, es[en].y=j;
}
sort(es+1,es+1+en);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++) t[i][j]=lower_bound(ls,ls+1+ln,t[i][j])-ls;
}
for(int i=1;i<=en;i++)
{
int ga=gf(es[i].x),gb=gf(es[i].y);
if(ga==gb) continue;
ff[ga]=gb; ds[++dn]=t[es[i].x][es[i].y];
adde(es[i].x,es[i].y);
}
dfs(1,0);
int maxn[2]={0,0};
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(col[i]==col[j]) maxn[col[i]]=max(maxn[col[i]],t[i][j]);
}
}
ds[++dn]=maxn[0]; ds[++dn]=maxn[1];
sort(ds+1,ds+1+dn); dn=unique(ds+1,ds+1+dn)-ds-1;
int ans=2000000033;
for(int i=0;i<=dn;i++)
{
int db=ds[i],qaq=db;
while(qaq>=0&&ls[db]+ls[qaq]>=ans) --qaq;
if(qaq<0||!ok(qaq,db)) continue;
int l=0,r=qaq;
while(l!=r)
{
int mid=(l+r)>>1;
if(ok(mid,db)) r=mid; else l=mid+1;
}
ans=min(ans,ls[db]+ls[l]);
}
printf("%d\n",ans);
main();
}