問題一覧 > 教育的問題

No.8011 Rearranging Items (Extra)

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 13
作問者 : ciel
お気に入りにしたユーザー ProblemId : 230 / 自分の提出
問題文最終更新日: 2026-06-27 22:23:39
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 102 (順位表) の他の問題:

Problem Statement

There are items numbered 0 to (N-1).
There is also a score table written in the format
item1 item2 score
(one such entry per line).
This means that when the items are arranged, you earn score points if item1 is placed before item2.

Given the score table, you want to rearrange the items appropriately so as to maximize the score earned. Output that score and the rearranged order.

* This is a version with stronger constraints of http://yukicoder.me/problems/209
(see the link above).

Input

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

$N$: the number of items
$M$: the number of lines in the score table
$item1_i\ item2_i\ score_i (1 \le i \le M)$: item 1, item 2, score

Constraints
$30<=N<=50$
$1<=M<=N*(N-1)$
$0<=item1,item2 < N$
$item1!=item2$
$1<=score<=10000$
No two different lines of the score table have both item1 and item2 equal.

Output

Total_Score
ordered_item[1] ... ordered_item[N]

$Total\_Score$: the total score
$ordered\_item_i\ (1 \le i \le N)$: the item to be placed in the i-th position Note that this is not the position where item i is placed.

About the Output

Your output is judged AC when all of the following conditions are satisfied.

  • The output has N+1 elements (or more)
  • Letting X be the maximum score obtained by running the intended solution's program 100 times, Total_Score is at least X*4/5 9/10 (*changed at 0:00)
  • ordered_item has no duplicates
  • The result calculated according to ordered_item equals Total_Score

Sample

Sample 1
Input
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
Output
300
3 2 1 0
(this_is_garbage)

Placing item 3 first, item 2 second, item 1 third, and item 0 fourth is optimal.
Although this sample outputs the order on the second line, each number may be separated by either a space or a newline.
Also, whatever is output as the (N+2)-th and later elements will not make the answer wrong.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。