No.8011 Rearranging Items (Extra)
タグ : / 解いたユーザー数 13
作問者 :
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/59/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もしくは右上の雲マークをクリックしてアカウントを作成してください。