CF1766F MCF

给定一个包含 $n$ 个顶点和 $m$ 条有向边的图。第 $i$ 条边从顶点 $x_i$ 指向顶点 $y_i$，容量为 $c_i$，权值为 $w_i$。没有边指向顶点 $1$，也没有边从顶点 $n$ 出发。图中不存在负权环（即无法从任意顶点出发经过若干条边回到自身且经过的所有边的权值之和为负数）。 你需要为每条边分配一个流量（一个在 $0$ 到其容量之间的整数，包括 $0$ 和容量）。对于除了 $1$ 和 $n$ 以外的每个顶点，流入该顶点的所有边的流量之和必须等于从该顶点流出的所有边的流量之和。设第 $i$ 条边的流量为 $f_i$，则流量的总代价为 $\sum\limits_{i=1}^{m} f_i w_i$。你需要找到一种流量分配方式，使总代价最小。 听起来很经典，对吧？不过，每条边的流量还要满足以下额外限制： - 如果 $c_i$ 是偶数，则 $f_i$ 必须是偶数； - 如果 $c_i$ 是奇数，则 $f_i$ 必须是奇数。 你能解决这个问题吗？

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 100$；$1 \le m \le 200$）。 接下来有 $m$ 行，每行包含四个整数 $x_i$、$y_i$、$c_i$ 和 $w_i$（$1 \le x_i \le n-1$；$2 \le y_i \le n$；$x_i \ne y_i$；$1 \le c_i \le 100$；$-100 \le w_i \le 100$）。这些整数描述了第 $i$ 条有向边。 输入的额外限制： - 图中不存在负权环。

如果不存在满足所有条件的流量分配方式，输出 Impossible。 否则，输出两行： - 第一行输出单词 Possible； - 第二行输出 $m$ 个整数 $f_1, f_2, \dots, f_m$。 如果有多组解，输出任意一组均可。注意，流量的总代价应最小。

由 ChatGPT 4.1 翻译