配点 : 1200 点
問題文
1 从 N 编号最多为 N 给出了由顶点组成的 DAG。 两侧是 M 书籍可用,i 第一条边是顶点 U_i 到顶点 这是面向 V_i 的一侧。 在这里,U_i<V_i 有保证。 每个顶点都写有一个整数,并且顶点 i 是一个整数 写入 A_i 。
顶点子集 定义 s ,f(s) 如下。
- f(s)=\sum_{v \in s} \min\{A_u\ |\ u \in s 和 DAG 中的顶点 您可以移至 u 到顶点 这是面向 v 请回答以下有关 \}
各整数 K=1,2,\cdots,N 的问题。 分解为
頂点集合 \{1,2,\cdots,N\} 除以 K 子集(可能为空)并将它们分为 比方说 X_1,X_2,\cdots,X_K 。 在分解过程中,每个顶点恰好是 1 包含在两个子集中。 求 \sum_{1 \leq i \leq K}f(X_i) 的最大可能值。
制約
- 1 \leq N \leq 80
- 0 \leq M \leq 160
- 1 \leq A_i \leq 80
- 1 \leq U_i < V_i \leq N
- (U_i,V_i) \neq (U_j,V_j) (i \neq j)
- 所有输入值均为整数 按此顺序打印
入力
输入是按以下格式从标准输入给出的。
N M A_1 A_2 \cdots A_N U_1 V_1 U_2 V_2 \vdots U_M V_M
出力
各 K=1,2,\cdots,N 的答案。
入力例 1
4 4 1 2 3 4 1 2 1 3 2 4 3 4
出力例 1
4 8 10 10
各 K 的最优解(示例)如下。
- K=1 : X_1=\{1,2,3,4\}
- K=2 : X_1=\{1\},X_2=\{2,3,4\}
- K=3 : X_1=\{1\},X_2=\{2,3\},X_3=\{4\}
- K=4 : X_1=\{1\},X_2=\{2\},X_3=\{3\},X_4=\{4\}
入力例 2
10 9 22 7 20 26 1 11 7 1 15 10 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
出力例 2
49 104 120 120 120 120 120 120 120 120
入力例 3
15 13 20 12 14 20 22 20 26 34 40 42 44 60 45 69 73 1 14 2 5 2 8 2 9 2 12 2 15 4 7 6 12 7 9 8 15 10 15 11 12 13 14
出力例 3
317 513 541 541 541 541 541 541 541 541 541 541 541 541 541
入力例 4
20 31 54 12 12 26 7 6 38 51 29 52 70 49 67 65 80 67 54 77 74 73 1 2 2 3 3 4 1 5 2 6 5 6 3 7 6 7 4 8 7 8 5 9 6 10 9 10 7 11 10 11 8 12 11 12 9 13 10 14 13 14 11 15 14 15 12 16 15 16 13 17 14 18 17 18 15 19 18 19 16 20 19 20
出力例 4
190 749 872 935 961 963 963 963 963 963 963 963 963 963 963 963 963 963 963 963