TopCoder

User's AC Ratio

80.0% (20/25)

Submission's AC Ratio

33.8% (47/139)

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

3
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

4
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

For Testdata: 0 ~ 0, Score: 10
For Testdata: 0 ~ 1, Score: 15
For Testdata: 0 ~ 2, Score: 20
For Testdata: 0 ~ 3, Score: 25
For Testdata: 0 ~ 4, Score: 30
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 65536 262144
1 2000 65536 262144
2 2000 65536 262144
3 3000 65536 262144
4 800 65536 262144