最大流算法，Dinic，ISAP

最大流Dinic算法：

1、先利用BFS对残余网络分层（一个节点的层数就是它到源点最少要经过的边数）

2、分层完了以后，从源点开始，利用DFS从前一层向后一层反复寻找增广路。

算法时间的复杂度为n*n*m（n是点数，m是边数）

poj1273 最大流算法模板题目（Dinic算法实现）

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<string>
#include<stack>
#include<set>
#define ll long long
#define MAX 1000
#define INF INT_MAX
#define eps 1e-8

using namespace std;

struct Edge{
	int from,to,cap,flow;
};

vector<int>G[MAX];
vector<Edge>edges;

int n;

void init(){
	for (int i=0; i<=n; i++) G[i].clear();
	edges.clear();
}

void addEdge(int from, int to, int cap){
	edges.push_back((Edge){from,to,cap,0});
	edges.push_back((Edge){to,from,0,0});   //添加反向边
	int k = edges.size();
	G[from].push_back(k-2);
	G[to].push_back(k-1);
}

int d[MAX];

bool bfs(int s, int t){
	bool vis[MAX];
	queue<int>q;
	memset(vis,false,sizeof(vis));
	d[s] = 0;
	q.push(s);
	vis[s] = true;
	while (!q.empty()){
		int u = q.front();
		q.pop();
		for (int i=0; i<G[u].size(); i++){
			Edge e = edges[G[u][i]];
			if (!vis[e.to] && e.cap > e.flow){
				vis[e.to] = true;
				d[e.to] = d[u] + 1;
				q.push(e.to);
			} 
		}
	}
	return vis[t];
}

int cur[MAX];

int dfs(int s, int t, int a){
	if (s == t || a == 0) return a;
	int flow = 0, f;
	for (int&i = cur[s]; i < G[s].size(); i++){
		Edge& e = edges[G[s][i]];
		if (d[s] + 1 == d[e.to] && (f = dfs(e.to,t,min(a,e.cap - e.flow))) > 0){
			e.flow += f;
			edges[G[s][i]^1].flow -= f;
			flow += f;
			a -= f;
			if (a == 0) break;
		}
	}
	return flow;
}

int Maxflow(int s, int t){          //s为源点，t为汇点的最大流
	int flow = 0;
	while (bfs(s,t)){
		memset(cur,0,sizeof(cur));
		flow += dfs(s,t,INF);
	}
	return flow;
}

int main(){
	int m;
	while (scanf("%d%d",&m,&n) != EOF){
		init();
		int x,y,z;
		for (int i=0; i<m; i++){
			scanf("%d%d%d",&x,&y,&z);
			addEdge(x,y,z);
		}
		printf("%d\n",Maxflow(1,n));
	}
	return 0;
}
           

ISAP算法+gap优化

poj1273最大流问题（ISAP实现）

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<stack>
#define ll long long
#define MAX 1000
#define eps 1e-8
#define INF INT_MAX

using namespace std;

struct Edge{
	int from, to,cap,flow;
};

vector<int>G[MAX],T[MAX];  //T用来记录G的转置，用于下面逆向bfs遍历图
vector<Edge>edges;

int n;

void init(){
	for (int i=0; i<=n; i++){
		G[i].clear();
		T[i].clear();
	}
	edges.clear();
}

void addEdge(int from, int to, int cap){
	edges.push_back((Edge){from,to,cap,0});
	edges.push_back((Edge){to,from,0,0});
	int k = edges.size();
	G[from].push_back(k-2);
	G[to].push_back(k-1);
}

int d[MAX];

void bfs(int s, int t){
	bool vis[MAX];
	queue<int>q;
	memset(vis,false,sizeof(vis));
	q.push(s);
	d[s] = 0;
	vis[s] = true;
	while (!q.empty()){
		int u = q.front();
		q.pop();
		for (int i=0; i<T[u].size(); i++){
			int v = T[u][i];
			if (!vis[v]){
				d[v] = d[u] + 1;
				vis[v]  =  true;
				q.push(v);
			}
		}
	}
}

int p[MAX],num[MAX],cur[MAX];

int Augment(int s, int t){
	int x = t, a = INF;
	while (x != s){
		Edge& e = edges[p[x]];
		a = min(a,e.cap - e.flow);
		x = edges[p[x]].from;
	}
	x = t;
	while (x != s){
		edges[p[x]].flow += a;
		edges[p[x]^1].flow -= a;
		x = edges[p[x]].from;
	}
	return a;
}

int Maxflow(int s, int t){
	int flow = 0;
	bfs(t,s);                //逆向bfs  
	memset(num,0,sizeof(num));
	for (int i=1; i<=n; i++) num[d[i]]++;   //注意此处i应该为节点的编号的变化范围
	int x = s;
	memset(cur,0,sizeof(cur));
	while (d[s] < n){                      //此处n应该为节点的数量
		if (x == t){
			flow += Augment(s,t);
			x = s;
		}
		int ok = 0;
		for (int i=cur[x]; i<G[x].size(); i++){
			Edge& e = edges[G[x][i]];
			if (e.cap > e.flow && d[x] == d[e.to] + 1){
				ok = 1;
				p[e.to] = G[x][i];
				cur[x] = i;
				x = e.to;
				break;
			}
		}
		if (!ok){
			int m = n-1;
			for (int i=0; i<G[x].size(); i++){
				Edge& e = edges[G[x][i]];
				if (e.cap > e.flow) m = min(m,d[e.to]);
			}
			if (--num[d[x]] == 0) break;       //gap优化，能使时间复杂度降低100倍左右
			num[d[x] = m+1]++;
			cur[x] = 0;
			if (x != s) x = edges[p[x]].from;
		}
	}
	return flow;
}

int main(){
	int m;
	while (scanf("%d%d",&m,&n) != EOF){
		int x,y,z;
		init();
		for (int i=0; i<m; i++){
			scanf("%d%d%d",&x,&y,&z);
			addEdge(x,y,z);
			T[y].push_back(x);
		}
		printf("%d\n",Maxflow(1,n));
	}
	return 0;
}