Contents
Problem
給出網路上所有的機器連線，要將老闆的主機和中央伺服器間的連線切斷，問最少花費。
邊就是拆掉線的花費、圖中的點也會有權重(也就是拆除主機)。
Solution
最小割 => 最大流。
由於點上也有花費，我們將所有點轉化成 IN 和 OUT。假設 1, 3 相通：
3_out -> 1_in <-> 1_out -> 3_in
3_in <-> 3_out
就像是把 (1_in <-> 1_out) 視為 1 一樣(中間的邊就是點的花費)，
如此也同時完成 1 <-> 3 。
接著就是做 Edmonds-Karp Algo. 或 Dinic Algo. 了，要注意點的數量由於 IN 和 OUT 會多一倍。
(我這邊是連續兩個兩個擺)
ref: http://www.csie.ntnu.edu.tw/~u91029/Flow.html#1
Code
Dinic Algo.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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
using namespace std;
int M, W;
int adj[N][N]; //residue capacity, adjacent matrix
int d[N];
int visited[N];
int parent[N]; //for dfs(stack)
inline int input()
{
int n = 0;
char c;
while ((c = getchar()) <= '9' && c >= '0')
n = n * 10 + c - '0';
return n;
}
void BFS(int s, int t)
{
fill(d, d + N, 1e9);
memset(visited, false, sizeof visited);
queue<int> Q;
Q.push(s);
d[s] = 0;
visited[s] = true;
while (!Q.empty())
{
int now = Q.front();
Q.pop();
for (int i = 1; i <= OUT(M); ++i)
{
if (adj[now][i] > 0 && !visited[i])
{
visited[i] = true;
d[i] = d[now] + 1;
Q.push(i);
if (i == t)
return;
}
}
}
}
//recursive verion
int DFS(int from, int t, int df)
{
if (from == t)
return df;
for (int i = 1; i <= OUT(M); ++i)
{
if (adj[from][i] > 0 && d[from] + 1 == d[i] && !visited[i])
{
int f;
visited[i] = true;
if ((f = DFS(i, t, min(df, adj[from][i]))) != 0)
{
adj[from][i] -= f;
adj[i][from] += f;
return f;
}
}
}
return 0;
}
//stack version
/*int DFS(int s, int t)
{
memset(parent, -1, sizeof parent);
int df = 1e9;
stack<int> stk;
parent[s] = s;
stk.push(s);
while (!stk.empty())
{
int now = stk.top();
stk.pop();
for (int i = 1; i <= OUT(M); ++i)
{
if (adj[now][i] > 0 && d[now] + 1 == d[i] && parent[i] == -1)
{
df = min(df, adj[now][i]);
parent[i] = now;
stk.push(i);
if (t == i)
{
for (int from = parent[t], to = t; from != to; from = parent[to = from])
{
adj[from][to] -= df;
adj[to][from] += df;
}
return df;
}
}
}
}
return 0;
}*/
int main()
{
//freopen("test.out", "w", stdout);
while (scanf("%d%d ", &M, &W) && (M || W))
{
adj[IN(1)][OUT(1)] = adj[OUT(1)][IN(1)] = 1e9; //s, boss
adj[IN(M)][OUT(M)] = adj[OUT(M)][IN(M)] = 1e9; //t, central
int m1, m2, c;
for (int i = 0; i < M - 2; ++i)
{
//scanf("%d%d",&m1,&c);
m1 = input();
c = input();
adj[IN(m1)][OUT(m1)] = adj[OUT(m1)][IN(m1)] = c;
}
for (int i = 0; i < W; ++i)
{
//scanf("%d%d%d",&m1,&m2,&c);
m1 = input();
m2 = input();
c = input();
//m2_out -> m1_in, m1_out -> m2_in
adj[OUT(m2)][IN(m1)] = adj[OUT(m1)][IN(m2)] = c;
}
//Dinic Algo.
int flow = 0;
while (true)
{
int s = OUT(1), t = IN(M);
BFS(s, t);
if (d[t] == 1e9)
break;
int f = 0;
while (true)
{
memset(visited, false, sizeof visited);
if ((f = DFS(s, t, 1e9)) != 0)
//if ((f = DFS(s, t)) != 0)
flow += f;
else
break;
}
}
printf("%d\n", flow);
//init
for (int i = 0; i <= OUT(M); ++i)
memset(adj[i], 0, sizeof adj[i]);
}
return 0;
}
Edmonds-Karp Algo.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
using namespace std;
int M, W;
int adj[N][N]; //residue capacity
int parent[N];
inline int input()
{
int n = 0;
char c;
while ((c = getchar()) <= '9' && c >= '0')
n = n * 10 + c - '0';
return n;
}
void BFS(int s, int t)
{
memset(parent, 0, sizeof parent);
queue<int> Q;
Q.push(s);
parent[s] = s;
while (!Q.empty() && !parent[t])
{
int now = Q.front();
Q.pop();
for (int i = 1; i <= OUT(M); ++i)
{
if (adj[now][i] > 0 && !parent[i])
{
Q.push(i);
parent[i] = now;
if (i == t)
break;
}
}
}
}
int main()
{
while (scanf("%d%d ", &M, &W) && (M || W))
{
adj[IN(1)][OUT(1)] = adj[OUT(1)][IN(1)] = 1e9; //s, boss
adj[IN(M)][OUT(M)] = adj[OUT(M)][IN(M)] = 1e9; //t, central
int m1, m2, c;
for (int i = 0; i < M - 2; ++i)
{
//scanf("%d%d",&m1,&c);
m1 = input();
c = input();
adj[IN(m1)][OUT(m1)] = adj[OUT(m1)][IN(m1)] = c;
}
for (int i = 0; i < W; ++i)
{
//scanf("%d%d%d",&m1,&m2,&c);
m1 = input();
m2 = input();
c = input();
//m2_out -> m1_in, m1_out -> m2_in
adj[OUT(m2)][IN(m1)] = adj[OUT(m1)][IN(m2)] = c;
}
//Edmonds-Karp Algo.
int flow = 0;
while (true)
{
int s = OUT(1), t = IN(M);
BFS(s, t);
if (!parent[t])
break;
/*for(int from = parent[t],to = t; from!=to; from = parent[to = from])
printf("%d -> %d\n",from,to);*/
int new_f = 1e9;
for (int from = parent[t], to = t; from != to; from = parent[to = from])
new_f = min(adj[from][to], new_f);
for (int from = parent[t], to = t; from != to; from = parent[to = from])
{
adj[from][to] -= new_f;
adj[to][from] += new_f;
}
flow += new_f;
}
printf("%d\n", flow);
//init
for (int i = 0; i <= OUT(M); ++i)
memset(adj[i], 0, sizeof adj[i]);
}
return 0;
}