回分類題庫
h208: D.分裁判問題
關鍵字: NPSC 2019 高中組初賽

測資點 : 10 | Time Limit : 15000 ms | Memory Limit : 128000 KB
Accepted : 2 Times / 2 Users | Submit : 24 Times / 6 Users | Accepted rate : 33%
題目加入時間 : 2020-05-14 13:39

Content: 简体中文

傳說中,累積參加 20 次 NPSC (National Problem Solving Contest),就會獲得最終大賽NPSC(National Problem Setting Contest) 的門票!

但是 NPSC 每 20 年才會舉辦一次,而且每次僅能有 N 位參賽者。參加 NPSC 這個最高殿堂是每個 NPSC 裁判的心願(也只有身為 NPSC 裁判,才有可能參加 20 年 NPSC)。正巧,今年剛好有 2N 個裁判累積參加滿 20 次 NPSC ,獲得了參加 NPSC 的資格。

身為 NPSC 的主辦,你希望最終來參加的是萬中選一的選手,因此,你決定將這 2N 位符合資格的 NPSC 裁判分為兩隊,分別有 N 位裁判。為了使這 2N 位裁判能使出渾身解術來競爭這 20 年一次的 NPSC 參賽權,你事先調查了這 2N 個裁判兩兩之間的競爭指數,你希望分成兩隊之後,在不同隊伍間的裁判兩兩競爭指數的和能越大越好。但光是規劃這 20 年一次的NPSC,就已經讓你傷透腦筋,因此,你決定寫個程式來幫你找出最大可能的競爭指數和。 

Input:

輸入第一行,包含一個正整數 T,代表接下來有 T 組測試資料。

每組測試資料第一行,包含一個正整數 N,代表有 N 位裁判能獲得 NPSC 的參賽權。接下來 2N行,每行包含 2N 個以空格隔開的非負整數 vij,代表第 i 位裁判與第 j 位裁判間的競爭指數。 

Output:

針對每組測試資料輸出一行包含一個整數,代表最大可能的競爭指數總和。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
1
1
0 3
3 0

Sample Output :

3

Hint :

Author :

NPSC 2019 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum