MCF

题意翻译

- 你需要解决一个有源汇最小费用可行流问题。 - 但是，容量与流量的奇偶性必须相同。 - 点数在 $2\sim100$ 范围内，边数在 $1\sim200$ 范围内，容量在 $1\sim100$ 范围内，费用在 $-100\sim100$ 范围内。 - 图中没有负环。

题目描述

You are given a graph consisting of $ n $ vertices and $ m $ directed arcs. The $ i $ -th arc goes from the vertex $ x_i $ to the vertex $ y_i $ , has capacity $ c_i $ and weight $ w_i $ . No arc goes into the vertex $ 1 $ , and no arc goes from the vertex $ n $ . There are no cycles of negative weight in the graph (it is impossible to travel from any vertex to itself in such a way that the total weight of all arcs you go through is negative). You have to assign each arc a flow (an integer between $ 0 $ and its capacity, inclusive). For every vertex except $ 1 $ and $ n $ , the total flow on the arcs going to this vertex must be equal to the total flow on the arcs going from that vertex. Let the flow on the $ i $ -th arc be $ f_i $ , then the cost of the flow is equal to $ \sum \limits_{i = 1}^{m} f_i w_i $ . You have to find a flow which minimizes the cost. Sounds classical, right? Well, we have some additional constraints on the flow on every edge: - if $ c_i $ is even, $ f_i $ must be even; - if $ c_i $ is odd, $ f_i $ must be odd. Can you solve this problem?

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 2 \le n \le 100 $ ; $ 1 \le m \le 200 $ ). Then $ m $ lines follow. The $ i $ -th of them contains four integers $ x_i $ , $ y_i $ , $ c_i $ , and $ 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 $ ). These integers describe the $ i $ -th arc. Additional constraints on the input: - there are no negative cycles in the graph.

输出格式

If a flow satisfying all of the constraints does not exist, print Impossible. Otherwise, print two lines: - the first line should contain one word Possible; - the second line should contain $ m $ integers $ f_1, f_2, \dots, f_m $ . If there are multiple answers, print any of them. Note that the cost of the flow should be minimized.

输入输出样例

输入样例 #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

**MCF 题目大意及输入输出数据格式**

**题目大意：**
你需要解决一个有源汇的最小费用可行流问题，但是流量的奇偶性必须与容量的奇偶性相同。点数在 $2 \le n \le 100$ 范围内，边数在 $1 \le m \le 200$ 范围内，容量在 $1 \le c_i \le 100$ 范围内，费用在 $-100 \le w_i \le 100$ 范围内。图中没有负环。

**输入格式：**
第一行包含两个整数 $n$ 和 $m$。
接下来 $m$ 行，每行包含四个整数 $x_i, y_i, c_i, w_i$，描述第 $i$ 条弧。

**输出格式：**
如果不存在满足所有约束的流，输出 "Impossible"。
否则，输出两行：
- 第一行输出 "Possible"；
- 第二行输出 $m$ 个整数 $f_1, f_2, \dots, f_m$。

如果有多个答案，输出其中任意一个。注意流的总费用应该最小化。

**输入输出样例：**
见原网页内容。**MCF 题目大意及输入输出数据格式** **题目大意：** 你需要解决一个有源汇的最小费用可行流问题，但是流量的奇偶性必须与容量的奇偶性相同。点数在 $2 \le n \le 100$ 范围内，边数在 $1 \le m \le 200$ 范围内，容量在 $1 \le c_i \le 100$ 范围内，费用在 $-100 \le w_i \le 100$ 范围内。图中没有负环。 **输入格式：** 第一行包含两个整数 $n$ 和 $m$。 接下来 $m$ 行，每行包含四个整数 $x_i, y_i, c_i, w_i$，描述第 $i$ 条弧。 **输出格式：** 如果不存在满足所有约束的流，输出 "Impossible"。 否则，输出两行： - 第一行输出 "Possible"； - 第二行输出 $m$ 个整数 $f_1, f_2, \dots, f_m$。 如果有多个答案，输出其中任意一个。注意流的总费用应该最小化。 **输入输出样例：** 见原网页内容。