題目描述
小涵很喜歡電腦遊戲，這些天他正在玩一個叫做《三國》的遊戲。
在遊戲中，小涵和計算機各執一方，組建各自的軍隊進行對戰。遊戲中共有 NN 位武将（NN為偶數且不小于44），任意兩個武将之間有一個“默契值”，表示若此兩位武将作為一對組合作戰時，該組合的威力有多大。遊戲開始前，所有武将都是自由的（稱為自由武将，一旦某個自由武将被選中作為某方軍隊的一員，那麼他就不再是自由武将了），換句話說，所謂的自由武将不屬于任何一方。
遊戲開始，小涵和計算機要從自由武将中挑選武将組成自己的軍隊，規則如下：小涵先從自由武将中選出一個加入自己的軍隊，然後計算機也從自由武将中選出一個加入計算機方的軍隊。接下來一直按照“小涵→計算機→小涵→……”的順序選擇武将，直到所有的武将被雙方均分完。然後，程式自動從雙方軍隊中各挑出一對默契值最高的武将組合代表自己的軍隊進行二對二比武，擁有更高默契值的一對武将組合獲勝，表示兩軍交戰，擁有獲勝武将組合的一方獲勝。
已知計算機一方選擇武将的原則是盡量破壞對手下一步将形成的最強組合，它采取的具體政策如下：任何時刻，輪到計算機挑選時，它會嘗試将對手軍隊中的每個武将與目前每個自由武将進行一一配對，找出所有配對中默契值最高的那對武将組合，并将該組合中的自由武将選入自己的軍隊。 下面舉例說明計算機的選将政策，例如，遊戲中一共有66個武将，他們互相之間的默契值如下表所示：
雙方選将過程如下所示：
小涵想知道，如果計算機在一局遊戲中始終堅持上面這個政策，那麼自己有沒有可能必勝？如果有，在所有可能的勝利結局中，自己那對用于比武的武将組合的默契值最大是多少？
假設整個遊戲過程中，對戰雙方任何時候均能看到自由武将隊中的武将和對方軍隊的武将。為了簡化問題，保證對于不同的武将組合，其默契值均不相同。
輸入輸出格式
輸入格式：
共 N 行。
第一行為一個偶數 NN，表示武将的個數。
第 22行到第 NN行裡，第i+1i+1行有N_iNi個非負整數，每兩個數之間用一個空格隔開，表示ii号武将和i+1,i+2,…,Ni+1,i+2,…,N号武将之間的默契值（0≤0≤默契值≤1,000,000,000≤1,000,000,000）。
輸出格式：
共 11 或 22行。
若對于給定的遊戲輸入，存在可以讓小涵獲勝的選将順序，則輸出11，并另起一行輸出所有獲勝的情況中，小涵最終選出的武将組合的最大默契值。如果不存在可以讓小涵獲勝的選将順序，則輸出 00。
輸入輸出樣例
輸入樣例#1： 複制
6
5 28 16 29 27
23 3 20 1
8 32 26
33 11
12
輸出樣例#1： 複制
1
32
輸入樣例#2： 複制
8
42 24 10 29 27 12 58
31 8 16 26 80 6
25 3 36 11 5
33 20 17 13
15 77 9
4 50
19 輸出樣例#2： 複制
1
77 說明
【資料範圍】
對于40\%40%的資料有 N≤10N≤10。
對于70\%70%的資料有N≤18N≤18。
對于 100\%100%的資料有 N≤500N≤500。
#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define REP(i,N) for(int i=0;i<(N);i++)
#define CLR(A,v) memset(A,v,sizeof A)
//////////////////////////////////
#define inf 0x3f3f3f3
const int N=500+5;
const int M=10*N;
int mp[N][N];
int main()
{
int n;
RI(n);
rep(i,1,n)
rep(j,i+1,n)
{
RI(mp[i][j]);
mp[j][i]=mp[i][j];
}
int ans=0;
rep(i,1,n)
{
sort(mp[i]+1,mp[i]+1+n);
ans=max(ans,mp[i][n-1]);
}
cout<<1<<endl;
cout<<ans;
return 0;
} View Code