Network flow
最大流问题
有向图，单源点，单汇点，边权为容量。求源到汇的最大流量。
-
Residual Network
For a path from source to target, subtract it from the current graph and add its reverse path.
Reverse edges provide the ability to cancel this path. (push the flow back/rearrange flow)
-
Ford-Fulkerson
Using DFS to find augmenting path.
\(O(Ef)\). \(f\) is the max flow.
-
Edmonds-Karp Algorithm
using BFS instead of DFS.
\(O(VE^2)\)
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int inf = 0x3f3f3f3f; const int maxv = 100; int V; int G[maxv][maxv]; // adjancency matrix int vis[maxv], pre[maxv]; int augment(int s, int t){ queue<int> q; memset(vis, 0, sizeof(vis)); memset(pre, -1, sizeof(pre)); vis[s] = 1; q.push(s); bool found = false; // bfs to find path from s to t while(!q.empty()){ int u = q.front(); q.pop(); for(int i=0; i<V; i++){ if(G[u][i]>0 && !vis[i]){ pre[i] = u; vis[i]=1; if(i==t){ found = true; break; } else q.pish(i); } } } if(!found) return 0; int mnflow = inf; int u = t; // find the narrowest edge in the found path while(pre[u] != -1){ mnflow = min(mnflow, G[pre[u]][u]); u = pre[u]; } // modify capacity & add reverse edge u = t; while(pre[u] != -1){ G[pre[u]][u] -= mnflow; G[u][pre[u]] += mnflow; u = pre[u]; } return mnflow; } int edmondskarp(int s, int t){ int mxflow = 0; int aug; while(aug = argument()){ mxflow += aug; } return mxflow; }
-
Dinic Algorithm
further decreasing times to call BFS.
\(O(V^2E)\)
// Drianage ditches POJ #include <iostream> #include <deque> #include <cstring> #include <algorithm> using namespace std; const int inf = 0x3f3f3f3f; const int maxv = 205; int V, E, s, t; int G[maxv][maxv]; // adjancency matrix int vis[maxv], dep[maxv]; bool bfs(){ int depth = 0; deque<int> q; memset(dep, -1, sizeof(dep)); dep[s]=0; q.push_back(s); while(!q.empty()){ int u = q.front(); q.pop_front(); for(int i=1; i<=V; i++){ if(G[u][i]>0 && dep[i]==-1){ dep[i] = dep[u]+1; if(i == t) return true; else q.push_back(i); } } } return false; } long long dinic(){ long long mxflow = 0; deque<int> q; while(bfs()){ q.push_back(s); memset(vis, 0, sizeof(vis)); vis[s] = 1; while(!q.empty()){ int u = q.back(); // u is target if(u == t){ int mnflow = inf; int v; // mnflow_start_vertex for(int i=1; i<q.size(); i++){ int vs = q[i-1]; int ve = q[i]; if(G[vs][ve]>0 && mnflow>G[vs][ve]){ mnflow = G[vs][ve]; v = vs; } } for(int i=1; i<q.size(); i++){ int vs = q[i-1]; int ve = q[i]; G[vs][ve] -= mnflow; G[ve][vs] += mnflow; } mxflow += mnflow; // pop back while(!q.empty() && q.back() != v){ vis[q.back()] = 0; q.pop_back(); } } // u is not target else{ // only add one point in the next layer to stack. bool found = false; for(int i=1; i<=V; i++){ if(G[u][i]>0 && dep[i] == dep[u]+1 && !vis[i]){ vis[i] = 1; q.push_back(i); found = true; break; } } // can't find such point. if(!found) q.pop_back(); } } } return mxflow; } int main(){ while(cin>>E>>V){ memset(G, 0, sizeof(G)); int a, b, c; for(int i=0; i<E; i++){ cin>>a>>b>>c; G[a][b] += c; } s = 1; t = V; cout<<dinic()<<endl; } }
-
Merge Vertex
For example ACM Compuer factory, there are two correct graphs:
Examples
-
ACM Computer factory
难在建图：
- 把每一个机器分成两个点，输入与产出，用产量连接两个点。
- 总源点，总汇点。分别与各个源点，汇点连接无穷边。
- 如何回溯maxflow的每条边：保存旧数组，相减即可。
#include <iostream>
#include <deque>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxv = 55*2;
const int maxp = 15;
int V, s, t;
int nodes[maxv][maxp];
int G[maxv][maxv]; // adjancency matrix
int GG[maxv][maxv]; // copy of G
int vis[maxv], dep[maxv];
bool bfs() {
int depth = 0;
deque<int> q;
memset(dep, -1, sizeof(dep));
dep[s] = 0;
q.push_back(s);
while (!q.empty()) {
int u = q.front(); q.pop_front();
for (int i = 0; i <= 2*V+1; i++) {
if (G[u][i] > 0 && dep[i] == -1) {
dep[i] = dep[u] + 1;
if (i == t) return true;
else q.push_back(i);
}
}
}
return false;
}
int dinic() {
int mxflow = 0;
deque<int> q;
while (bfs()) {
q.push_back(s);
memset(vis, 0, sizeof(vis));
vis[s] = 1;
while (!q.empty()) {
int u = q.back();
// u is target
if (u == t) {
int mnflow = inf;
int v; // mnflow_start_vertex
for (int i = 1; i < q.size(); i++) {
int vs = q[i - 1];
int ve = q[i];
if (G[vs][ve] > 0 && mnflow > G[vs][ve]) {
mnflow = G[vs][ve];
v = vs;
}
}
for (int i = 1; i < q.size(); i++) {
int vs = q[i - 1];
int ve = q[i];
G[vs][ve] -= mnflow;
G[ve][vs] += mnflow;
}
mxflow += mnflow;
// pop back
while (!q.empty() && q.back() != v) {
vis[q.back()] = 0;
q.pop_back();
}
}
// u is not target
else {
// only add one point in the next layer to stack.
bool found = false;
for (int i = 0; i <= 2*V+1; i++) {
if (G[u][i] > 0 && dep[i] == dep[u] + 1 && !vis[i]) {
vis[i] = 1;
q.push_back(i);
found = true;
break;
}
}
// can't find such point.
if (!found) q.pop_back();
}
}
}
return mxflow;
}
int P;
int main() {
cin >> P >> V;
memset(G, 0, sizeof(G));
memset(nodes, 0, sizeof(nodes));
// Input
for (int i = 0; i < V; i++) {
cin >> G[i][i + V];
for (int j = 0; j < P; j++) cin >> nodes[i][j];
for (int j = 0; j < P; j++) cin >> nodes[i + V][j];
}
// link output to input
for (int i = V; i < 2 * V; i++) {
for (int j = 0; j < V; j++) {
bool fit = true;
for (int k = 0; k < P; k++) {
if (nodes[j][k] == 2) continue;
else if (nodes[j][k] != nodes[i][k]) {
fit = false;
break;
}
}
if (fit) G[i][j] = inf;
}
}
// ultra-source, ultra-target
s = 2 * V;
t = 2 * V + 1;
// link to s
for (int i = 0; i < V; i++) {
bool fit = true;
for (int k = 0; k < P; k++) {
if (nodes[i][k] == 1) {
fit = false;
break;
}
}
if (fit) G[s][i] = inf;
}
// link to t
for (int i = V; i < 2 * V; i++) {
bool fit = true;
for (int k = 0; k < P; k++) {
if (nodes[i][k] != 1) {
fit = false;
break;
}
}
if (fit) G[i][t] = inf;
}
// copy
memcpy(GG, G, sizeof(G));
// dinic
int mxflow = dinic();
// retrieve maxflow
vector<int> vs, ve, vv;
for (int i = V; i < 2 * V; i++) {
for (int j = 0; j < V; j++) {
int diff = GG[i][j] - G[i][j];
if (diff > 0) {
vs.push_back(i - V + 1);
ve.push_back(j + 1);
vv.push_back(diff);
}
}
}
// Output
cout << mxflow <<" "<< vv.size() << endl;
for (int i = 0; i < vv.size(); i++)
cout << vs[i] << " " << ve[i] << " " << vv[i] << endl;
}
- Optimal Milking
#include <iostream>
#include <deque>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxv = 250;
int V, E, s, t;
int G[maxv][maxv]; // adjancency matrix
int vis[maxv], dep[maxv];
bool bfs() {
int depth = 0;
deque<int> q;
memset(dep, -1, sizeof(dep));
dep[s] = 0;
q.push_back(s);
while (!q.empty()) {
int u = q.front(); q.pop_front();
for (int i = 0; i < V; i++) {
if (G[u][i] > 0 && dep[i] == -1) {
dep[i] = dep[u] + 1;
if (i == t) return true;
else q.push_back(i);
}
}
}
return false;
}
int dinic() {
int mxflow = 0;
deque<int> q;
while (bfs()) {
q.push_back(s);
memset(vis, 0, sizeof(vis));
vis[s] = 1;
while (!q.empty()) {
int u = q.back();
// u is target
if (u == t) {
int mnflow = inf;
int v; // mnflow_start_vertex
for (int i = 1; i < q.size(); i++) {
int vs = q[i - 1];
int ve = q[i];
if (G[vs][ve] > 0 && mnflow > G[vs][ve]) {
mnflow = G[vs][ve];
v = vs;
}
}
for (int i = 1; i < q.size(); i++) {
int vs = q[i - 1];
int ve = q[i];
G[vs][ve] -= mnflow;
G[ve][vs] += mnflow;
}
mxflow += mnflow;
// pop back
while (!q.empty() && q.back() != v) {
vis[q.back()] = 0;
q.pop_back();
}
}
// u is not target
else {
// only add one point in the next layer to stack.
bool found = false;
for (int i = 0; i < V; i++) {
if (G[u][i] > 0 && dep[i] == dep[u] + 1 && !vis[i]) {
vis[i] = 1;
q.push_back(i);
found = true;
break;
}
}
// can't find such point.
if (!found) q.pop_back();
}
}
}
return mxflow;
}
int K, C, M;
int graph[maxv][maxv];
int dist[maxv][maxv];
void floyd() {
memcpy(dist, graph, sizeof(dist));
int V = K + C;
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
if (dist[i][j] == 0) dist[i][j] = inf;
for (int u = 0; u < V; u++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] > dist[i][u] + dist[u][j]) {
dist[i][j] = dist[i][u] + dist[u][j];
}
}
}
}
}
int check(int mxdist) {
memset(G, 0, sizeof(G));
V = K + C + 2;
s = V - 2;
t = V - 1;
for (int i = 0; i < K; i++) G[i][V - 1] = M;
for (int i = K; i < K + C; i++) {
G[V - 2][i] = 1;
for (int j = 0; j < K; j++)
if (dist[i][j] <= mxdist) G[i][j] = 1;
}
return dinic();
}
int main() {
cin >> K >> C >> M;
for (int i = 0; i < K + C; i++)
for (int j = 0; j < K + C; j++)
cin >> graph[i][j];
floyd();
int l = 0, r = 200 * 250 * 2;
while (l <= r) {
int m = (l + r) / 2;
int flow = check(m);
// cout << "check " << m << " mxflow " << flow << endl;
if (flow == C) r = m - 1;
else l = m + 1;
}
cout << l << endl;
}