No.519 アイドルユニット

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 52
作問者 : horiesinitihoriesiniti / テスター : tubo28tubo28

0 ProblemId : 1195 / 出題時の順位表

問題文

Aさんはあるアイドル事務所のマネージャーです。
このアイドル事務所にはn人(2の倍数人)のアイドルが登録しています。
全員2人組(ペア)にして売り出すことになりました。
全部の2人には相性があり、2人の相性度の高さがそのままアイドルの人気度になります。
2人をa,bとして相性度を求める関数をfとするとf(a,b)=f(b,a)となります。
全2人の組み合わせでの相性度がn*nの表で与えられる。(f(a,a)は不可能なので-1が与えられる。)
全ペアの人気度の合計が最大になるようにペアを作った時の合計人気度を答えよ。
(ヒント 最も重い採点データn=24をRubyで安定して一秒以内が想定解です、C++では0.1秒以内)

入力

$n$
$F11$ $\dots$ $F1n$
$\dots$
$Fn1$ $\dots$ $Fnn$

1<n<=24

0<=fij<=1000

アイドルの人数n人が一行目に与えられる。 続くn行にn*nの表として、アイドルの相性表が与えられる。
一行目がアイドル1で2行目がアイドル2、、、n行目がアイドルN
一列目がアイドル1で2列目がアイドル2、、、n列目がアイドルN
例えばアイドル1とアイドル3の相性を見るには1行目の3列目か3行目の1列目を見ればよい。 アイドル2とアイドル7の相性を見るには2行目の7列目か7行目の2列目を見ればよい。 $S$と一行に全ペアの人気度の合計値が最大になるようにペアを作った時の人気度を表示せよ。

出力

S 最後に改行してください。

サンプル

サンプル1
入力
4
-1 16 15 38
16 -1 22 17
15 22 -1 19
38 17 19 -1
出力
60

アイドル1と4の組で38、アイドル2と3の組で22。 これで全ペアが出来上がり相性度=人気度の合計は60である。

サンプル2
入力
6
-1 14 29 35 39 8
14 -1 35 41 34 3
29 35 -1 14 21 21
35 41 14 -1 12 42
39 34 21 12 -1 28
8 3 21 42 28 -1
出力
116

アイドル6とアイドル4が42、アイドル2とアイドル3が35、アイドル1とアイドル5が39

合計は42+35+39=116となる。

提出ページヘ