AT_jsc2024_final_f Max of Sum of Reachable Min

给定一个包含 $N$ 个顶点的有向无环图（DAG），顶点编号为 $1$ 到 $N$。图中有 $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\mid u \in s$ 且在 DAG 中可以从顶点 $u$ 到达顶点 $v$的 $ \}$。 对于每个整数 $K=1,2,\cdots,N$，请回答下列问题。 请将顶点集合 $\{1,2,\cdots,N\}$ 分成 $K$ 个（可以为空）子集，记为 $X_1,X_2,\cdots,X_K$。分割时应保证每个顶点恰好属于一个子集。求所有 $\sum_{1 \leq i \leq K}f(X_i)$ 的最大可能值。

输入以如下格式从标准输入读取： > $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 对于每个 $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\}$ ### 数据范围 - $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$） - 所有输入值均为整数。 由 ChatGPT 5 翻译