33OJ
登录 注册

#P4126. [AHOI2009] 最小割

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

[AHOI2009] 最小割

题目描述

A,BA,B 两个国家正在交战,其中 AA 国的物资运输网中有 NN 个中转站,MM 条单向道路。设其中第 i(1≤i≤M)i(1\le i\le M) 条道路连接了 vi,uiv_i,u_i 两个中转站,那么中转站 viv_i 可以通过该道路到达 uiu_i 中转站,如果切断这条道路,需要代价 cic_i。

现在 BB 国想找出一个路径切断方案,使中转站 ss 不能到达中转站 tt,并且切断路径的代价之和最小。

小可可一眼就看出,这是一个求最小割的问题。但爱思考的小可可并不局限于此。现在他对每条单向道路提出两个问题:

  • 问题一:是否存在一个最小代价路径切断方案,其中该道路被切断?
  • 问题二:是否对任何一个最小代价路径切断方案,都有该道路被切断?

现在请你回答这两个问题。

输入格式

第一行有 44 个正整数,依次为 N,M,s,tN,M,s,t。

第 22 行到第 (M+1)(M+1) 行每行 33 个正整数 v,u,cv,u,c,表示 vv 中转站到 uu 中转站之间有单向道路相连,单向道路的起点是 vv,终点是 uu,切断它的代价是 c(1≤c≤100000)c(1\le c\le100000)。

注意:两个中转站之间可能有多条道路直接相连。 同一行相邻两数之间可能有一个或多个空格。

输出格式

对每条单向边,按输入顺序,依次输出一行,包含两个非 00 即 11 的整数,分别表示对问题一和问题二的回答(其中输出 11 表示是,输出 00 表示否)。 同一行相邻两数之间用一个空格隔开,每行开头和末尾没有多余空格。

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

提示

设第 (i+1)(i+1) 行输入的边为 ii 号边,那么 {1,2},{6,7},{2,4,6}\{1,2\},\{6,7\},\{2,4,6\} 是仅有的三个最小代价切割方案。它们的并是 {1,2,4,6,7}\{1,2,4,6,7\},交是 {∅}\{\varnothing \}。

测试数据规模如下表所示

数据编号 NN MM 数据编号 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