「BZOJ1797」[Ahoi2009]Mincut 最小割

Description

A,BA,B两个国家正在交战,其中A国的物资运输网中有N个中转站,M条单向道路。设其中第i(1iM)i (1\leq i\leq M)条道路连接了vi,uiv_i,u_i两个中转站,那么中转站viv_i可以通过该道路到达uiu_i中转站,如果切断这条道路,需要代价cic_i。现在BB国想找出一个路径切断方案,使中转站ss不能到达中转站tt,并且切断路径的代价之和最小。
小可可一眼就看出,这是一个求最小割的问题。但爱思考的小可可并不局限于此。现在他对每条单向道路提出两个问题:

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

Input

第一行有44个正整数,依次为N,M,sN,M,stt。第22行到第(M+1)(M+1)行每行33个正 整数v,u,cv,u,c表示vv中转站到uu中转站之间有单向道路相连,单向道路的起点是vv, 终点是uu,切断它的代价是c(1c100000)c(1\leq c\leq100000)
注意:两个中转站之间可能有多条道路直接相连。 同一行相邻两数之间可能有一个或多个空格。

Output

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

Sample Input

1
2
3
4
5
6
7
8
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

Sample Output

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

HINT

设第(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 \}

Solution

跑一遍最大流,以代价cic_i为容量,在残余网络上跑tarjan。
对于一条边:
满足条件一当:

  • 它是满流的
  • 残余网络中的sccusccvscc_u\neq scc_v

满足条件二当:

  • 它是满流的
  • 参与网络中sccu=sccsscc_u=scc_ssccv=scctscc_v=scc_t
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#include<queue>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 5000, M = 70000*2;
int n, m, s, t;
struct Edge {
int u, v, nxt, f;
}e[M*2];
int en, head[N];
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].f = z;
e[++en].u = y, e[en].v = x, e[en].nxt = head[y], head[y] = en, e[en].f = 0;
}
const int inf = 1e8 + 7;
int d[N];
int dinic(int x, int flow) {
if(x == t) return flow;
int rest = flow, k = 0;
for(int i = head[x]; i && rest; i = e[i].nxt)
if(e[i].f && d[e[i].v] == d[x] + 1) {
int y = e[i].v;
k = dinic(y, min(e[i].f, rest));
e[i].f -= k;
e[i ^ 1].f += k;
rest -= k;
}
return flow - rest;
}
int st[N], top, dfn[N], low[N], num;
bool vis[N];
int cnt, scc[N];

void tarjan(int x) {
st[++top] = x;
vis[x] = 1;
dfn[x] = low[x] = ++num;
for(int i = head[x]; i; i = e[i].nxt) if(e[i].f){
int y = e[i].v;
if(!dfn[y]) {
tarjan(y);
low[x] = min(low[x], low[y]);
} else if(vis[y]) low[x] = min(low[x], dfn[y]);
}
if(dfn[x] == low[x]) {
int y; ++cnt;
do {
y = st[top--];
scc[y] = cnt;
vis[y] = 0;
}while(y != x);
}
}
bool bfs() {
queue<int>q;
q.push(s);
for(int i = 1; i <= n; ++i) d[i] = 0;
d[s] = 1;
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = head[x]; i;i = e[i].nxt) if(e[i].f){
int y = e[i].v;
if(!d[y]) {
d[y] = d[x] + 1;
q.push(y);
if(y == t) return 1;
}
}
}
return 0;
}
bool ans1[M], ans2[M];
int f = 0;
int main() {
en = 1;
n = read(), m = read(), s = read(), t = read();
for(int i = 1; i <= m; ++i) {
int x = read(), y = read(), z = read();
addedge(x, y, z);
}
int tmp;
while(bfs()) while(tmp = dinic(s, inf)) f += tmp;
for(int i = 1; i <= n; ++i) if(!dfn[i]) tarjan(i);
for(int i = 1; i <= m; ++i) if(e[i <<1].f == 0 && scc[e[i<<1].u] != scc[e[i<<1].v]) ans1[i] = 1;
for(int i = 1; i <= m; ++i) if(e[i<<1].f == 0 && scc[e[i<<1].u] == scc[s] && scc[e[i<<1].v] ==scc[t]) ans2[i] = 1;
for(int i = 1; i <= m; ++i)
printf("%d %d\n", ans1[i], ans2[i]);
return 0;
}