33OJ
登录 注册

#P4126. [AHOI2009] 最小割

    ID: 4839 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 显示难度省选/NOI− 上传者: 标签>2009并查集各省省选安徽强连通分量最小割

[AHOI2009] 最小割

Problem Description

Countries A,BA, B are at war. In country AA’s supply transport network, there are NN transshipment stations and MM directed roads. Suppose the ii-th (1≤i≤M1\le i\le M) road connects stations vi,uiv_i, u_i, meaning that station viv_i can reach station uiu_i via this road. Cutting this road costs cic_i.

Country BB wants to find a set of roads to cut so that station ss cannot reach station tt, and the total cutting cost is minimized.

Xiao Keke immediately recognizes that this is a minimum cut problem. But the thoughtful Xiao Keke goes further. For each directed road, he asks two questions:

  • Question 1: Does there exist a minimum-cost cut in which this road is cut?
  • Question 2: Is this road cut in every minimum-cost cut?

Please answer these two questions.

Input Format

The first line contains 44 positive integers: N,M,s,tN, M, s, t.

Each of the next MM lines contains 33 positive integers v,u,cv, u, c, indicating a directed road from station vv to station uu, with cutting cost cc (1≤c≤1000001\le c\le 100000).

Note: There may be multiple roads directly connecting the same pair of stations. Within the same line, adjacent numbers may be separated by one or more spaces.

Output Format

For each directed road, in the input order, output one line containing two integers, each either 00 or 11. They are the answers to Question 1 and Question 2 respectively (11 means yes, 00 means no). Separate the two numbers on the same line with a single space, and do not print extra spaces at the beginning or end of the line.

6 7 1 6
1 2 3
1 3 2
2 4 4
2 5 1
3 5 5
4 6 2
5 6 3
1 0
1 0
0 0
1 0
0 0
1 0
1 0

Hint

Let the edge given on line (i+1)(i+1) be labeled as edge ii. Then {1,2},{6,7},{2,4,6}\{1,2\}, \{6,7\}, \{2,4,6\} are the only three minimum-cost cuts. Their union is {1,2,4,6,7}\{1,2,4,6,7\}, and their intersection is ∅\varnothing.

The scale of the testdata is shown in the table below.

Testdata ID NN MM Testdata ID NN MM
11 1010 5050 66 10001000 2000020000
22 2020 200200 77 4000040000
33 200200 20002000 88 20002000 5000050000
44 99 30003000 6000060000
55 10001000 2000020000 1010 40004000

Translated by ChatGPT 5