1418 . 交大都是雷
TopCoder
Tags
Description
交大參加ACM-ICPC 的隊伍名稱都跟雷電有關：因為「交大都是雷」。因此不可避免的，上場比賽難免也會雷雷的，交大的教練感到非常苦惱。參加ACM-ICPC 的隊伍，⼀隊需要三個人，⽽根據不禮貌的想像，一個隊伍「雷」的程度，是由隊員兩兩之間的交互作用引發的「雷力」大小決定。譬如說NCTU_Thor 這一隊由aaaaajack、leopan0922、lclan 三個人組成，aaaaajack 跟leopan0922 之間產生的「雷力」為a、leopan0922 跟lclan 之間產生的「雷力」為b、lclan 跟aaaaajack 之間產生的「雷力」為c，則NCTU_Thor 這一隊的「內部雷力」為a + b + c，將與實際「雷」的程度成正比。教練請示過校門口土地公後，總算知道學生與學生之間兩兩交互作用所產生的雷力數值。請幫交大的教練寫一個程式，找出最理想的組隊方式，也就是將所有隊伍的「總內部雷力」降到最低。
Input Format
第一行有一整數T 代表有多少測試資料，T 最多20。
每⼀筆測試資料的第一行有一個數字N，代表有多少隊員，N 必然被3 整除，且不⼤於21。方便起見，將參賽學生由1 到N 編號。
接下來N ⾏中的第i ⾏，有N 個數字，其中第j 個就是記錄學生i 與學生j 之間的雷⼒Ri,j。
測試資料中，雷力的數值必是不⼤於100 的非負整數、Ri,i = 0 且Ri,j = Rj,i。如果不是這樣，出題老師就太雷了，這⼀題會送分。
Output Format
對每⼀個測試資料，輸出一行，內含一個數字，代表將隊伍分好後，可達到的最低「總內部雷力」。
Sample Input 1
3
0 1 1
1 0 2
1 2 0
6
0 1 1 4 1 3
1 0 2 1 4 2
1 2 0 3 2 4
4 1 3 0 1 1
1 4 2 1 0 2
3 2 4 1 2 0
6
0 1 1 4 1 3
1 0 2 1 4 2
1 2 0 3 2 4
4 1 3 0 4 4
1 4 2 4 0 5
3 2 4 4 5 0
Sample Output 1
8
11
Hints
本題共有五組小題。每組可有多個測試輸入檔，全部答對該組才得分。
第⼀組10 分，所有的測資N <= 9。
第⼆組15 分，所有的測資N <= 12。
第三組20 分，所有的測資N <= 15。
第四組25 分，所有的測資N <= 18。
第五組30 分，所有的測資N <= 21。
Problem Source
Set by 殿仁．王
105學年度臺北市資訊學科能力 - 環境練習題組
取自104 學年度普通型高級中學資訊學科能⼒競賽決賽 — 環境練習題組
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 0~1 | 15 |
| 3 | 0~2 | 20 |
| 4 | 0~3 | 25 |
| 5 | 0~4 | 30 |