BZOJ 1797][AHOI 2009] 最小割

题目大意

给定一个 \(n\) 个节点、\(m\) 条有向带权边的图以及起点 \(s\) 与终点 \(t\),对于每条边,询问它是否有可能 \(s\)\(t\) 之间的最小割的割边,以及它是否会出现在所有最小割的割边中。

\(1 \leqslant n \leqslant 4,000\)

\(1 \leqslant m \leqslant 60,000\)

题目链接

BZOJ 1797

题解

先跑一遍最大流,对残量网络跑 Tarjan。如果一条边没有满流,则它不会是最小割的割边;对于满流的边,两端在不同强连通块的是最小割的割边,若有 \(u.scc = s.scc\) 并且 \(v.scc = t.scc\),则它出现在所有最小割中。

代码

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <cstdio>
#include <climits>
#include <queue>
#include <stack>
#include <algorithm>
const int MAXN = 4005;
const int MAXM = 60005;
struct Edge;
struct Node {
Edge *e, *curr;
int level;
int dfn, low, belong;
bool ins;
} N[MAXN];
struct Edge {
Node *u, *v;
Edge *rev, *next;
int cap, flow;
Edge() {}
Edge(Node *u, Node *v, int cap) : u(u), v(v), cap(cap), flow(0), next(u->e) {}
} _pool[MAXM << 1], *_cur = _pool;
void addEdge(int u, int v, int cap) {
N[u].e = new (_cur++) Edge(&N[u], &N[v], cap);
N[v].e = new (_cur++) Edge(&N[v], &N[u], 0);
N[u].e->rev = N[v].e;
N[v].e->rev = N[u].e;
}
namespace Dinic {
bool makeLevelGraph(Node *s, Node *t, int n) {
for (int i = 1; i <= n; i++) N[i].level = 0;
std::queue<Node *> q;
q.push(s);
s->level = 1;
while (!q.empty()) {
Node *u = q.front();
q.pop();
for (Edge *e = u->e; e; e = e->next) {
if (e->cap > e->flow && e->v->level == 0) {
e->v->level = u->level + 1;
if (e->v == t) return true;
q.push(e->v);
}
}
}
return false;
}
int findPath(Node *s, Node *t, int limit = INT_MAX) {
if (s == t) return limit;
for (Edge *&e = s->curr; e; e = e->next) {
if (e->cap > e->flow && e->v->level == s->level + 1) {
int flow = findPath(e->v, t, std::min(limit, e->cap - e->flow));
if (flow > 0) {
e->flow += flow;
e->rev->flow -= flow;
return flow;
}
}
}
return 0;
}
int solve(int s, int t, int n) {
int res = 0;
while (makeLevelGraph(&N[s], &N[t], n)) {
for (int i = 1; i <= n; i++) N[i].curr = N[i].e;
int flow;
while ((flow = findPath(&N[s], &N[t])) > 0) res += flow;
}
return res;
}
}
namespace Tarjan {
int dfsClock, sccCnt;
void dfs(Node *u) {
u->dfn = u->low = ++dfsClock;
static std::stack<Node *> s;
s.push(u);
u->ins = true;
for (Edge *e = u->e; e; e = e->next) {
if (e->cap > e->flow) {
if (e->v->dfn == 0) dfs(e->v), u->low = std::min(u->low, e->v->low);
else if (e->v->ins) u->low = std::min(u->low, e->v->dfn);
}
}
if (u->dfn == u->low) {
Node *curr;
sccCnt++;
while (true) {
curr = s.top();
s.pop();
curr->ins = false;
curr->belong = sccCnt;
if (curr == u) break;
}
}
}
void findSCC(int n) {
dfsClock = sccCnt = 0;
for (int i = 1; i <= n; i++) if (N[i].dfn == 0) dfs(&N[i]);
}
}
int main() {
int n, m, s, t;
scanf("%d %d %d %d", &n, &m, &s, &t);
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
addEdge(u, v, w);
}
Dinic::solve(s, t, n);
Tarjan::findSCC(n);
for (int i = 0; i < m << 1; i += 2) {
Edge *e = &_pool[i];
if (e->cap > e->flow) {
puts("0 0");
continue;
}
printf("%d ", e->u->belong != e->v->belong ? 1 : 0);
printf("%d\n", e->u->belong == N[s].belong && e->v->belong == N[t].belong ? 1 : 0);
}
return 0;
}