定义集合S的价值D(S)为：

输入数据的第一行是一个整数n，代表元素个数。

 输出只有一行，一个整数，代表min{D(A)+D(B)}。

鸣谢qpswwww提供译文

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<ctime>//by NeighThorn#define inf 0x3f3f3f3fusing namespace std; const int maxn=400+5,maxm=200000+5; int id;int lala,fa[maxn],co[maxn];int C,tim,top,mp[maxn],dfn[maxn],low[maxn],stk[maxm],instk[maxn];int n,s1,s2,ans,cnt,len,w[maxn][maxn],hd[maxn],to[maxm],nxt[maxm]; struct M{         int x,y,v;         inline M(){};         M(int a,int b,int c){        x=a,y=b,v=c;    }         friend bool operator < (M a,M b){        if(a.v!=b.v)			return a.v>b.v;		if(a.x!=b.x)			return a.x>b.x;		return a.y>b.y;    }     }e[maxm]; inline int read(void){    char ch=getchar();int x=0;    while(!(ch>=‘0‘&&ch<=‘9‘)) ch=getchar();    while(ch>=‘0‘&&ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();    return x;   } inline void add(int x,int y){    to[cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt++;} inline void tarjan(int x){    low[x]=dfn[x]=++tim;stk[++top]=x;instk[x]=1;    for(int i=hd[x];i!=-1;i=nxt[i]){        if(!dfn[to[i]])            tarjan(to[i]),low[x]=min(low[x],low[to[i]]);        else if(instk[to[i]])            low[x]=min(low[x],dfn[to[i]]);    }    if(dfn[x]==low[x]){        C++;int tmp;        do{            tmp=stk[top--],instk[tmp]=0;mp[tmp]=C;        }while(tmp!=x);    }} inline bool check(void){    cnt=C=tim=top=0;    memset(mp,0,sizeof(mp));    memset(hd,-1,sizeof(hd));    memset(dfn,0,sizeof(dfn));    memset(low,0,sizeof(low));    memset(instk,0,sizeof(instk));    for(int i=1;i<n;i++)        for(int j=i+1;j<=n;j++){            if(w[i][j]>s1)                add(i<<1,j<<1|1),add(j<<1,i<<1|1);            if(w[i][j]>s2)                add(i<<1|1,j<<1),add(j<<1|1,i<<1);        }    for(int i=2;i<=(n<<1|1);i++)        if(!dfn[i]) tarjan(i);    for(int i=1;i<=n;i++)        if(mp[i<<1]==mp[i<<1|1])            return false;    return true;} inline int find(int x){    if(fa[x]==x)        return x;    int fx=find(fa[x]);    co[x]^=co[fa[x]];    return fa[x]=fx;}inline int calc(int x){	int l=0,r=x,res=-1;	while(l<=r){        int mid=(l+r)>>1;s2=mid;        if(check())            r=mid-1,res=mid;        else            l=mid+1;    }    return res;} signed main(void){    n=read();ans=inf;    if(n<=2) return puts("0"),0;    for(int i=1;i<n;i++)        for(int j=i+1;j<=n;j++)            w[i][j]=w[j][i]=read(),e[++lala]=M(i,j,w[i][j]);    sort(e+1,e+lala+1);for(int i=1;i<=n;i++) fa[i]=i;    for(int i=1,x,y,fx,fy,res;i<=lala;i++){        s1=e[i].v;x=e[i].x,y=e[i].y,fx=find(x),fy=find(y);        if(fx!=fy){        	res=calc(s1);        	if(res!=-1) ans=min(ans,s1+res);        	co[fx]=co[x]^co[y]^1;fa[fx]=fy;        }        else if(co[x]==co[y]){        	res=calc(s1);        	if(res!=-1) ans=min(ans,res+s1);			break;        }    }    printf("%d\n",ans);    return 0;}