← 返回题目列表

AtCoder · jsc2024_final_f

F. 可达到的最小值之和的最大值

中文机器翻译题面 查看原题

配点 : 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