CF1615H Reindeer Games

北极有 $n$ 只驯鹿，它们都在争夺 CodeNorses（一个受欢迎的竞技驯鹿游戏网站）首页上的“Top Reindeer”排行榜最高位置。有趣的是，“Top Reindeer”头衔只是根据点赞数来决定的，和它们在驯鹿游戏中的技能水平毫无关系，但它们依然极为重视这一头衔。 目前，第 $i$ 只驯鹿的分数为 $a_i$。你希望通过一些操作来影响排行榜。在一次操作中，你可以选择一只驯鹿，将它的分数增加或减少 $1$。分数可以为负数。 你有 $m$ 个关于最终分数的要求。每个要求由一个有序对 $(u, v)$ 给出，表示所有操作结束后，驯鹿 $u$ 的分数必须小于等于驯鹿 $v$ 的分数。 你的任务是用最少的操作次数，使得所有要求都被满足。

第一行包含两个整数 $n$ 和 $m$（$2\le n\le 1000$，$1\le m\le 1000$），分别表示驯鹿的数量和要求的数量。 第二行包含 $n$ 个整数 $a_1,\ldots, a_n$（$1\le a_i\le 10^9$），其中 $a_i$ 表示第 $i$ 只驯鹿当前的分数。 接下来的 $m$ 行描述了这些要求。 第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1\le u_i, v_i\le n$，$u_i\ne v_i$），表示第 $i$ 个要求涉及的两只驯鹿。

输出 $n$ 个整数 $b_1,\ldots, b_n$（$-10^{15}\le b_i\le 10^{15}$），其中 $b_i$ 表示所有操作结束后第 $i$ 只驯鹿的分数。 如果有多组最优解，你可以输出任意一组。 可以证明，始终存在一种最优解，使得所有 $|b_i|\le 10^{15}$。

由 ChatGPT 4.1 翻译