No.90 品物の並び替え

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

2 ProblemId : 209 / 出題時の順位表

問題文

ここに0番〜(N-1)番の品物がある。
また、
item1 item2 score
という形式で書かれた得点表がある。
品物を並べた時、item1がitem2よりも前であればscore点を獲得できるという意味である。

得点表が与えられるので、品物を適切に並び替えた時、獲得できる得点を最大化したい。そのときの得点を出力せよ。

注意:LL系の言語だと工夫しないといけないかもしれません。

入力

N M
item1[1] item2[1] score[1]
…
item1[M] item2[M] score[M]

N:品物の数
M:得点表の行数
item1[i] item2[i] score[i] (1<=i<=M): 品物1、品物2、得点

制約
2<=N<=9
1<=M<=N*(N-1)
0<=item1,item2<N
item1!=item2
1<=score<=10000

得点表の相異なる行において、item1とitem2がどちらも等しくなることはない。

出力

獲得できる最大得点を出力せよ。出力後は改行すること。

サンプル

サンプル1
入力
4 9
0 1 1
0 2 2
0 3 3
1 2 4
1 3 5
2 3 6
3 2 100
2 1 100
1 0 100
出力
300

3 2 1 0
と並べた時の300点が最大となる。

0 1 2 3
と並べた時、適用される数は6個だが、21点となり、最高点は得られないことに注意せよ。

提出ページヘ