翻车笔记_ [Ahoi2009] Mincut[网络流, 强连通分量]

看上去毫不相干的东西也许是正解

其实本来不想写的…毕竟看了题解很惭愧…但是今天又考了一个类似的…看上去还挺普遍挺套路的?

AHOI2009 Mincut

感谢Gay娘耐心的讲解

在残量网络上可以干很多有趣的事情…比如说求个方案或者跑个tarjan啥的…

我们在残量网络上跑tarjan(只关心flow < cap的边)

  • 如果一条边没有满流, 显然不会出现在任何割中
  • 如果一条边的fromto在一个强连通分量中, 那么这条边不满足条件1: 如那支灰色的流的前两条边, 和下面两条空流的蓝边在一个强连通分量中, 那么我就可以用底下的蓝边来替代这两条灰色的边, 而流量不变

看看这个

  • 如果一条边的froms在一个强连通分量里, tot在一个强连通分量里, 那么这条边满足条件2: froms在一个强连通分量中代表有至少两条路径可以走到from, 而且一条有流量一条没有流量(即确实可以通过这些在强连通分量里的路径到达from);tot在一个强连通分量理由同上; 所以不管割掉哪些满流的边, 都可以通过另外一条路径到达from, to也可以通过另外的路径到达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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#define MAXN (400000 + 5)
#define MAXM (600000 + 5)
#define INF (0x7ffffff)
#define rev(a) ((((a) - 1) ^ 1) + 1)
#define pbb pair<bool, bool>
#define mkp(a, b) make_pair(a, b)
using namespace std;
struct edg
{
int from, to, next, cap, flow, bh;
edg(): bh(0) {}
edg(int fr, int t, int ne, int ca, int fl): from(fr), to(t), next(ne), cap(ca), flow(fl) {}
}b[MAXM << 1];
int s, t, g[MAXN], cntb, n, bl[MAXN], dfn[MAXN], low[MAXN], cntdfn, dis[MAXN];
pbb ans[MAXN];
bool instack[MAXN];
stack<int> ss;
void tarjan(int dq)
{
bl[dq] = dq;
dfn[dq] = low[dq] = ++cntdfn;
ss.push(dq);
instack[dq] = true;
for (int i = g[dq]; i; i = b[i].next)
{
if (b[i].cap <= b[i].flow) continue;
if (!dfn[b[i].to])
{
tarjan(b[i].to);
low[dq] = min(low[dq], low[b[i].to]);
}
else if (instack[b[i].to])
{
low[dq] = min(low[dq], dfn[b[i].to]);
}
}
if (low[dq] == dfn[dq])
{
while (!ss.empty() && ss.top() != dq)
{
bl[ss.top()] = dq;
instack[ss.top()] = false;
ss.pop();
}
ss.pop();
instack[dq] = false;
}
}
bool bfs()
{
memset(dis, 0, sizeof(dis));
queue<int> q;
q.push(s);
dis[s] = 1;
while (!q.empty())
{
int dq = q.front();
q.pop();
for (int i = g[dq]; i; i = b[i].next)
{
if (!dis[b[i].to] && b[i].cap > b[i].flow)
{
dis[b[i].to] = dis[dq] + 1;
q.push(b[i].to);
}
}
}
return dis[t];
}
int dinic(int dq, int maxf)
{
if (dq == t || (!maxf))
return maxf;
int re = 0;
for (int i = g[dq]; i; i = b[i].next)
{
if (b[i].cap > b[i].flow && dis[b[i].to] == dis[dq] + 1)
{
int zl = dinic(b[i].to, min(b[i].cap - b[i].flow, maxf));
b[i].flow += zl;
b[rev(i)].flow -= zl;
maxf -= zl;
re += zl;
}
}
return re;
}
void solve()
{
while (bfs())
dinic(s, INF);
for (int i = 1; i <= n; i++)
if (!dfn[i])
tarjan(i);
for (int i = 1; i <= cntb; i++)
{
if (b[i].bh && b[i].flow == b[i].cap)
{
ans[b[i].bh] = mkp(false, false);
if (bl[b[i].from] != bl[b[i].to])
{
ans[b[i].bh].first = true;
if (bl[b[i].from] == bl[s] && bl[b[i].to] == bl[t])
ans[b[i].bh].second = true;
}
}
}
}
void adn(int from, int to, int cap)
{
b[++cntb] = edg(from, to, g[from], cap, 0);
g[from] = cntb;
}
int main()
{
int m;
scanf("%d%d%d%d", &n, &m, &s, &t);
for (int i = 1; i <= m; i++)
{
int srx, sry, srz;
scanf("%d%d%d", &srx, &sry, &srz);
adn(srx, sry, srz);
b[cntb].bh = i;
adn(sry, srx, 0);
}
solve();
for (int i = 1; i <= m; i++)
printf("%d %d\n", ans[i].first, ans[i].second);
return 0;
}

/*
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
*/

舞动的夜晚

感谢XP学长耐心的讲解

和上面那个题就非常的像了…

如果一条边没有满流, 而且他的首尾不在一个强连通分量中, 那么加上这条边就会使流量减少

看看这个

如果一条边被删掉了流量不变, 当且仅当他的fromto在一个强连通分量中, 因为如果这条边有流量, 就一定可以通过强连通分量中的另一条路径流过去, 否则删掉也没有任何影响

那么, 可以改变边的流量都是在强连通分量之间改变的, 如果一条边并不在强连通分量中, 而他的流量还是空的, 说明加上这条边就一定会使总流量减少

沙茶的 代码

注意别把反向边给加到ans里了…

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#define MAXN (100000 + 5)
#define MAXM (500000 + 5)
#define INF (0X7FFFFFF)
#define bh(a) ((a) + n)
#define rev(a) ((((a) - 1) ^ 1) + 1)
const int s = 0, t = MAXN - 1;
using namespace std;
struct edg
{
int from, to, next, cap, flow;
int bh;
}b[MAXM << 1];
int g[MAXN], cntb, belong[MAXN], dfn[MAXN], low[MAXN], cntdfn;
int dis[MAXN], n, m, tm;
stack<int> st;
bool ins[MAXN], ans[MAXN];
void adn(int from, int to, int cap)
{
b[++cntb].next = g[from];
b[cntb].from = from, b[cntb].flow = 0, b[cntb].to = to, b[cntb].cap = cap;
g[from] = cntb;
}
void tarjan(int dq)
{
low[dq] = dfn[dq] = ++cntdfn;
st.push(dq);
ins[dq] = true;
for (int i = g[dq]; i; i = b[i].next)
{
if (b[i].cap <= b[i].flow)
continue;
if (!dfn[b[i].to])
{
tarjan(b[i].to);
low[dq] = min(low[b[i].to], low[dq]);
}
else if (ins[b[i].to])
low[dq] = min(low[dq], dfn[b[i].to]);
}
if (low[dq] == dfn[dq])
{
while (!st.empty() && st.top() != dq)
{
ins[st.top()] = false;
belong[st.top()] = dq;
st.pop();
}
ins[dq] = false;
belong[dq] = dq;
if (!st.empty())
st.pop();
}
}
int dinic(int dq, int maxf)
{
if (dq == t || !maxf)
return maxf;
int re = 0;
for (int i = g[dq]; i; i = b[i].next)
{
if (b[i].cap > b[i].flow && dis[b[i].to] == dis[dq] + 1)
{
int zl = dinic(b[i].to, min(maxf, b[i].cap - b[i].flow));
b[i].flow += zl;
b[rev(i)].flow -= zl;
maxf -= zl;
re += zl;
}
}
return re;
}
int bfs()
{
memset(dis, 0, sizeof(dis));
queue<int> q;
q.push(s);
dis[s] = 1;
while (!q.empty())
{
int dq = q.front();
q.pop();
for (int i = g[dq]; i; i = b[i].next)
if (!dis[b[i].to] && b[i].cap > b[i].flow)
dis[b[i].to] = dis[dq] + 1, q.push(b[i].to);
}
return dis[t];
}
void solve()
{
memset(ins, false, sizeof(ins));
memset(ans, false, sizeof(ans));
while (bfs())
dinic(s, INF);
// printf("%d\n", dinic(s, INF));
for (int i = 1; i <= (n + m); i++)
if (!dfn[i])
tarjan(i);
for (int i = 1; i <= cntb; i++)
if (b[i].flow != b[i].cap && belong[b[i].from] != belong[b[i].to])
ans[b[i].bh] = true;
int pans = 0;
for (int i = 1; i <= tm; i++)
if (ans[i])
++pans;
printf("%d\n", pans);
for (int i = 1; i <= tm; i++)
if (ans[i])
printf("%d ", i);
}
int main()
{
freopen("d.in", "r", stdin);
freopen("d.out", "w", stdout);
scanf("%d%d%d", &n, &m, &tm);
for (int i = 1; i <= n; i++)
{
adn(s, i, 1);
adn(i, s, 0);
}
for (int i = 1; i <= m; i++)
{
adn(bh(i), t, 1);
adn(t, bh(i), 0);
}
for (int i = 1; i <= tm; i++)
{
int srx, sry;
scanf("%d%d", &srx, &sry);
adn(srx, bh(sry), 1);
adn(bh(sry), srx, 0);
b[cntb - 1].bh = i;
}
solve();
return 0;
}

/*
3 3 6
1 1
2 1
2 2
3 1
3 2
3 3
*/

By 智障 Cansult