← 返回题目列表

Codeforces · 1766/F

F. 最小费用流

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

给定一个由 $$$n$$$ 个顶点和 $$$m$$$ 有向弧组成的图。第 $$$i$$$ 弧从顶点 $$$x_i$$$ 到顶点 $$$y_i$$$,容量为 $$$c_i$$$,权重为 $$$w_i$$$。没有弧进入顶点 $$$1$$$,也没有弧从顶点 $$$n$$$ 出发。图中不存在负权重循环(不可能从任何顶点移动到其自身,从而使您经过的所有弧的总权重为负)。

您必须为每个弧分配一个流($$$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$$$ 行。其中第 $$$i$$$ 包含四个整数 $$$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。

否则,打印两行:

- 第一行应包含一个单词“可能”;
- 第二行应包含 $$$m$$$ 整数 $$$f_1, f_2, \dots, f_m$$$。

如果有多个答案,请打印其中任何一个。请注意,流量成本应最小化。

示例

输入 #1

3 3
1 2 3 -10
1 2 3 -15
2 3 2 0

输出 #1

Possible
1 1 2

输入 #2

3 3
1 2 3 -10
1 2 3 -15
2 3 3 0

输出 #2

Impossible

输入 #3

3 3
1 2 3 -10
1 2 3 -15
2 3 4 0

输出 #3

Possible
1 3 4

输入#4

6 7
5 6 9 -40
1 2 3 -10
1 4 5 20
4 5 7 30
2 5 1 -15
1 3 3 5
3 5 3 0

输出#4

Possible
5 1 1 1 1 3 3