#3830. [AHOI2009] 最小割

    ID: 3830 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>图结构网络流数据结构并查集强连通分量2009各省省选安徽缩点最大流最小割

[AHOI2009] 最小割

题目描述

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

现在B国想找出一个路径切断方案,使中转站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(1c100000)c(1≤c≤100000)

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

输出格式

对每条单向边,按输入顺序,依次输出一行,包含两个非0011的整数,分别表示对问题一和问题二的回答(其中输出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 \}

测试数据规模如下表所示

数据编号 N M 数据编号 N M
1 10 50 6 1000 20000
2 20 200 7 40000
3 200 2000 8 2000 50000
4 9 3000 60000
5 1000 20000 10 4000