I. Fold-Forkson Method
As long as there is an open path through the residual graph, send the minimum of the residual capacities on the path.
1. First, We use a general dfs to find the augmenting path.
2. When we finding augmenting paths with breadth-first search. Things get changed. && we got .. Edmonds_Karp Algorithm .
/*
ID: xiaodao
PROG: ditch
LANG: CPP
*/
#include
#include
using namespace std;
const int INF = 1000000;
const int N = 1001;
int stack[N], top; //Stack..
bool visited[N];
int C[N][N], F[N][N]; // Capacity, Flow..
int n, m, ans;
inline void push(int x){
//cout << x << endl;
stack[++top] = x;
visited[x] = true;
}
inline void pop(){
visited[stack[top]] = false;
top--;
}
inline bool empty(){
return top==-1;
}
void stat(){
ans = 0;
for (int i=2;i<=n;i++)
ans += F[1][i];
}
bool find_path(){
int cur[N];
memset(visited, false, sizeof(visited));
for (int i=1;i n) pop();
else{
push(v);
if (v == n) return true;
cur[u] = v + 1;
}
}
return false;
}
void add_path(){
int u, v; int delta = INF;
for (int i=0;i> m >> n;
int x, y, c;
for (int i=1;i<=m;i++){
scanf("%d%d%d", &x, &y, &c);
C[x][y] += c;
}
}
int main(){
freopen("ditch.in","r",stdin);
freopen("ditch.out","w",stdout);
init(); dfs_method();
cout << ans << endl;
}
/*
ID: xiaodao
PROG: ditch
LANG: CPP
*/
#include
#include
using namespace std;
const int INF = 1000000;
const int N = 1001;
struct rec{
int v, p, k;
// Vertex, Parient ,key
};
int C[N][N], F[N][N]; // Capacity, Flow..
bool V[N]; rec Q[N]; // Visited, Queue..
int head, tail;
int n, m, ans;
bool find_path(){
memset(V, false, sizeof(V));
Q[0].v = 1; Q[0].k = INF; V[1] = true;
head = 0; tail = 1;
int u, v;
while (head> m >> n;
int x, y, c;
for (int i=1;i<=m;i++){
scanf("%d%d%d", &x, &y, &c);
C[x][y] += c;
}
}
int main(){
freopen("ditch.in","r",stdin);
freopen("ditch.out","w",stdout);
init(); Edmonds_Karp();
cout << ans << endl;
}
II. Dinitz Blocking Flow Method
In each phase the algorithms builds a layered graph with breadth-first search on the residual graph.
/*
ID: xiaodao
PROG: ditch
LANG: CPP
*/
#include
#include
#include
using namespace std;
const int INF = 1000000;
const int N = 1001;
struct rec{
int v, p, k;
// Vertex, Key ...
// Point to key ...
};
int C[N][N], F[N][N]; // Capacity, Flow..
int L[N]; // Leval ...
int n, m, ans;
void stat(){
ans = 0;
for (int i=2;i<=n;i++)
ans += F[1][i];
}
void bfs(){
memset(L, -1, sizeof(L));
int Q[N], head, tail;
head = 0; tail = 1; Q[0] = 1;
L[1] = 0;
int u, v;
while (headn){
L[u] = -1;
top--;
}
else{
cache[u] = v+1; top++;
stack[top].v = v;
if (C[u][v] - F[u][v] < stack[top-1].k){
stack[top].k = C[u][v] - F[u][v];
stack[top].p = top-1;
}
else{
stack[top].k = stack[top-1].k;
stack[top].p = stack[top-1].p;
}
}
}
bfs();
}
stat();
}
void init(){
memset(C, 0, sizeof(C));
memset(F, 0, sizeof(F));
cin >> m >> n;
int x, y, c;
for (int i=1;i<=m;i++){
scanf("%d%d%d", &x, &y, &c);
C[x][y] += c;
}
}
int main(){
freopen("ditch.in","r",stdin);
freopen("ditch.out","w",stdout);
init(); dinic();
cout << ans << endl;
}
III. Push-Relabel Method.
Since 1976. A New Approach to the Maximum-Flow Problem ...
1. General push-relabel maximum flow algorithm.
2. Push-relabel algorithm with FIFO vertex selection rule...
(Although.. A still have some question between it and the Relabel_to_Frontalgorithm... )
/*
ID: xiaodao
PROG: ditch
LANG: CPP
*/
#include
#include
using namespace std;
const int INF = 1000000;
const int N = 1001;
int C[N][N], F[N][N]; // Capacity, Flow..
int H[N], E[N]; // .Height, Excess ...
int n, m, ans;
//bool sign;
void push(int u, int v, int delta){
F[u][v] += delta; F[v][u] -= delta;
E[u] -= delta; E[v] += delta;
}
void relabel(int u){
H[u]++;
}
void discharge(int u){
for (int v=1;v<=n;v++){
if (H[u] == H[v] + 1 && F[u][v] < C[u][v]){
push(u, v, min(E[u], C[u][v] - F[u][v]));
if (E[u]==0) return;
}
}
relabel(u);
}
void push_relabel(){
memset(E, 0, sizeof(E));
memset(H, 0, sizeof(H));
E[1] = INF; H[1] = n;
for (int i=2;i<=n;i++){
if (C[1][i] > 0) {
push(1, i, C[1][i]);
if (i!=n) H[i] = 1;
}
}
do{
//As long as there is legal push or relabel operation
for (int u=2;u> m >> n;
int x, y, c;
for (int i=1;i<=m;i++){
scanf("%d%d%d", &x, &y, &c);
C[x][y] += c;
}
}
int main(){
freopen("ditch.in","r",stdin);
freopen("ditch.out","w",stdout);
init(); push_relabel();
cout << E[n] << endl;
}
/*
ID: xiaodao
PROG: ditch
LANG: CPP
*/
#include
#include
using namespace std;
const int INF = 1000000;
const int N = 1001;
int C[N][N], F[N][N]; // Capacity, Flow..
int H[N], E[N]; // .Height, Excess ...
int Q[N]; int head, tail; // Queue...
int n, m, ans;
void push(int u, int v, int delta){
F[u][v] += delta; F[v][u] -= delta;
E[u] -= delta; E[v] += delta;
}
void relabel(int u){
/*
H[u] = INF;
for (int v=1;v<=n;v++){
if (F[u][v] < C[u][v])
H[u] = min(H[u], H[v]+1);
}
*/
H[u]++;
}
void discharge(int u){
for (int v=1;v<=n;v++){
if (H[u] == H[v] + 1 && F[u][v] < C[u][v]){
if (v!=n && E[v] == 0) {
Q[tail] = v;
tail = (tail + 1) % N;
}
push(u, v, min(E[u], C[u][v] - F[u][v]));
if (E[u] == 0) return;
}
}
Q[tail] = u;
tail = (tail + 1) % N;
relabel(u);
}
void push_relabel(){
memset(E, 0, sizeof(E));
memset(H, 0, sizeof(H));
E[1] = INF; H[1] = n;
head = 0; tail = 0;
for (int i=2;i<=n;i++){
if (C[1][i] > 0) {
push(1, i, C[1][i]);
if (i!=n) H[i] = 1, Q[tail++] = i;
}
}
while (head!=tail){
discharge(Q[head]);
head = (head + 1) % N;
}
}
void init(){
memset(C, 0, sizeof(C));
memset(F, 0, sizeof(F));
cin >> m >> n;
int x, y, c;
for (int i=1;i<=m;i++){
scanf("%d%d%d", &x, &y, &c);
C[x][y] += c;
}
}
int main(){
freopen("ditch.in","r",stdin);
freopen("ditch.out","w",stdout);
init(); push_relabel();
cout << E[n] << endl;
}
/*
ID: xiaodao
PROG: ditch
LANG: CPP
*/
#include
#include
#include
using namespace std;
const int INF = 1000000;
const int N = 1001;
int C[N][N], F[N][N]; // Capacity, Flow..
int H[N], E[N]; // .Height, Excess ...
int n, m, ans;
bool changed;
void push(int u, int v, int delta){
F[u][v] += delta; F[v][u] -= delta;
E[u] -= delta; E[v] += delta;
}
void relabel(int u){
/*
H[u] = INF;
for (int v=1;v<=n;v++){
if (F[u][v] < C[u][v])
H[u] = min(H[u], H[v]+1);
}*/
H[u]++;
}
void discharge(int u){
if (E[u]==0){
changed = false;
return;
}
changed = true;
for (int v=1;v<=n;v++){
if (u == v) continue;
if (H[u] > H[v] && F[u][v] < C[u][v]){
push(u, v, min(E[u], C[u][v] - F[u][v]));
if (E[u]==0) {changed = false; return;}
}
}
relabel(u);
}
void relabel_to_front(){
//Relabel-to-front algorithm, ie. using FIFO heuristic
//1.Send as much flow from s as possible.
memset(E, 0, sizeof(E));
memset(H, 0, sizeof(H));
E[1] = INF; H[1] = n;
for (int i=2;i<=n;i++){
if (C[1][i] > 0) {
push(1, i, C[1][i]);
if (i!=n) H[i] = 1;
}
}
//2.Build a list of all nodes except s and t.
list L;
for (int i=2;i::iterator it=L.begin();
while (it!=L.end()){
//1.Discharge the current node.
discharge(*it);
//2.If the height of the current node changed:
if (changed){
L.push_front(*it); L.erase(it);
it = L.begin();
}
else
it++;
}
}
void init(){
memset(C, 0, sizeof(C));
memset(F, 0, sizeof(F));
cin >> m >> n;
int x, y, c;
for (int i=1;i<=m;i++){
scanf("%d%d%d", &x, &y, &c);
C[x][y] += c;
}
}
int main(){
freopen("ditch.in","r",stdin);
freopen("ditch.out","w",stdout);
init(); relabel_to_front();
cout << E[n] << endl;
}
External link :
http://en.wikipedia.org/wiki/Push-relabel_maximum_flow_algorithm
http://www.nocow.cn/index.php/Translate:USACO/ditch
