Flow Problem
Time Limit: 5000/5000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 17030 Accepted Submission(s): 8021
Problem Description Network flow is a well-known difficult problem for ACMers. Given a graph, your task is to find out the maximum flow for the weighted directed graph.
Input The first line of input contains an integer T, denoting the number of test cases.
For each test case, the first line contains two integers N and M, denoting the number of vertexes and edges in the graph. (2 <= N <= 15, 0 <= M <= 1000)
Next M lines, each line contains three integers X, Y and C, there is an edge from X to Y and the capacity of it is C. (1 <= X, Y <= N, 1 <= C <= 1000)
Output For each test cases, you should output the maximum flow from source 1 to sink N.
Sample Input
2
3 2
1 2 1
2 3 1
3 3
1 2 1
2 3 1
1 3 1
Sample Output
Case 1: 1
Case 2: 2
Author HyperHexagon
Source HyperHexagon's Summer Gift (Original tasks)
原題連結：http://acm.hdu.edu.cn/showproblem.php?pid=3549
最大流入門題：最大流問題在劉汝佳的《算法競賽入門經典》和《算法競賽入門經典訓練指南》中均有纖細介紹。
競賽中通常可以使用Dinic算法和ISAP算法，但是Ford-Fulkerson算法了解起來簡單一點。
最大流問題吧算法代碼當做模闆，根據具體問題去建圖就可以了。
AC代碼1.Ford-Fulkerson算法
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxn=20;
const int maxm=1050;
const int INF=0x3f3f3f3f;
int t;
int n,m;
bool vis[maxn];
int Case=0;
struct node
{
int to,cap;
unsigned int rev;
};
vector<node> G[maxn];
void add_edge(int from,int to,int cap)
{
G[from].push_back({to,cap,G[to].size()});
G[to].push_back({from,0,G[from].size()-1});
}
int dfs(int v,int t,int f)
{
if(v==t) return f;
vis[v]=true;
for(unsigned int i=0;i<G[v].size();i++)
{
node &e=G[v][i];
if(!vis[e.to]&&e.cap>0)
{
int d=dfs(e.to,t,min(f,e.cap));
if(d>0)
{
e.cap-=d;
G[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int max_flow(int s,int t)
{
int flow=0;
while(1)
{
memset(vis,0,sizeof(vis));
int f=dfs(s,t,INF);
if(f==0) return flow;
flow+=f;
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++) G[i].clear();
for(int i=0;i<m;i++)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
add_edge(x,y,c);
}
printf("Case %d: %d\n",++Case,max_flow(1,n));
}
return 0;
}
AC代碼2：Dinic算法
/**
* 行有餘力，則來刷題！
* 部落格連結:http://blog.csdn.net/hurmishine
* 個人部落格網站:http://wuyunfeng.cn/
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=15+5;
const int INF=0x3f3f3f3f;
struct Edge
{
int from,to,cap,flow;//起點，終點，容量，流量
Edge(){}
Edge(int from,int to,int cap,int flow):from(from),to(to),cap(cap),flow(flow){}
};
struct Dinic
{
int n,m,s,t; //節點數，邊數(包括反向弧），源點編号和彙點編号
vector<Edge>edge; //邊表。edge[e]和edge[e^1]互為反向弧
vector<int>G[maxn]; //鄰接表，G[i][j]表示節點i的第j條邊在數組中的序号
bool vis[maxn]; //BFS使用，标記一個節點是否被周遊過
int d[maxn]; //從起點到i點的距離
int cur[maxn]; //目前弧下标
void init(int n,int s,int t)
{
this->n=n;
this->s=s;
this->t=t;
for(int i=1;i<=n;i++)
G[i].clear();
edge.clear();
}
void addEdge(int from,int to,int cap)
{
//edge.push_back((Edge){from,to,cap,0});
//edge.push_back((Edge){to,from,0,0});
edge.push_back( Edge(from,to,cap,0) );
edge.push_back( Edge(to,from,0,0) );
m=edge.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
bool BFS()
{
memset(vis,0,sizeof(vis));
queue<int>q;//
q.push(s);
d[s]=0;
vis[s]=true;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=0;i<G[x].size();i++)
{
Edge& e=edge[G[x][i]];
if(!vis[e.to]&&e.cap>e.flow)//隻考慮殘量網絡中的弧
{
vis[e.to]=true;
d[e.to]=d[x]+1;
q.push(e.to);
}
}
}
return vis[t];
}
int DFS(int x,int a)
{
if(x==t||a==0)
return a;
int flow=0,f;
for(int &i=cur[x];i<G[x].size();i++)//從上次考慮的弧
{
Edge& e=edge[G[x][i]];
if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0)
{
e.flow+=f;
edge[G[x][i]^1].flow-=f;
flow+=f;
a-=f;
if(a==0)
break;
}
}
return flow;
}
int MaxFlow()
{
int flow=0;
while(BFS())
{
memset(cur,0,sizeof(cur));
flow+=DFS(s,INF);
}
return flow;
}
}Dinic;
int main()
{
//freopen("C:\\Users\\hncu_acm\\Desktop\\data.txt","r",stdin);
int T,n,m;
int kase=0;
cin>>T;
while(T--)
{
cin>>n>>m;
Dinic.init(n,1,n);
int u,v,w;
while(m--)
{
cin>>u>>v>>w;
Dinic.addEdge(u,v,w);
}
printf("Case %d: %d\n",++kase,Dinic.MaxFlow());
}
return 0;
}
AC代碼3：ISAP算法：
//http://blog.csdn.net/x920405451x/article/details/39747081
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <functional>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctime>
#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long ll;
//typedef pair<int,int> pii;
#define INF 1e9
#define MAXN 10000
#define MAXM 100
const int maxn = 20;
const int mod = 1000003;
#define eps 1e-6
#define pi 3.1415926535897932384626433
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define scan(n) scanf("%d",&n)
#define scan2(n,m) scanf("%d%d",&n,&m)
#define scans(s) scanf("%s",s);
#define ini(a) memset(a,0,sizeof(a))
#define FILL(a,n) fill(a,a+maxn,n)
#define out(n) printf("%d\n",n)
//ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b);}
#define mk(n,m) make_pair(n,m)
using namespace std;
struct Edge
{
int from,to,cap,flow;
Edge(int f = 0, int t = 0, int c = 0, int fl = 0):from(f),to(t),cap(c),flow(fl) {}
};
int n,m;
vector<int> G[maxn];
vector<Edge> edges;
bool vis[maxn];
int d[maxn]; //殘量網絡中從節點i到彙點t的距離
int cur[maxn]; //目前弧下标
int p[maxn]; //可增廣路上的上一條弧
int num[maxn]; //距離标号計數
struct ISAP
{
void init(int n)
{
edges.clear();
rep(i,n+3) G[i].clear();
FILL(d,n+1);
}
void add(int from,int to,int cap)
{
edges.push_back(Edge(from, to, cap, 0));
edges.push_back(Edge(to, from, 0, 0));
int p = edges.size();
G[from].push_back(p - 2);
G[to].push_back(p - 1);
}
bool bfs(int s,int t)
{
memset(vis, 0, sizeof(vis));
queue<int> q;
q.push(t);
vis[t] = 1;
d[t] = 0;
while (!q.empty())
{
int u = q.front();
q.pop();
for (int i = 0; i < G[u].size(); i++)
{
Edge &e = edges[G[u][i]^1]; //這條弧的反弧
if (!vis[e.from] && e.cap > e.flow)
{
vis[e.from] = true;
d[e.from] = d[u] + 1;
q.push(e.from);
}
}
}
return vis[s];
}
// 增廣
int augment(int s,int t)
{
int u = t, df = INF;
// 從彙點到源點通過 p 追蹤增廣路徑, df 為一路上最小的殘量
while (u != s)
{
Edge &e = edges[p[u]];
df = min(df, e.cap - e.flow);
u = edges[p[u]].from;
}
u = t;
// 從彙點到源點更新流量
while (u != s)
{
edges[p[u]].flow += df;
edges[p[u]^1].flow -= df;
u = edges[p[u]].from;
}
return df;
}
int maxflow(int s,int t)
{
int flow = 0;
bfs(s,t);
memset(num, 0, sizeof(num));
for (int i = 0; i < n; i++) num[d[i]]++;
int u = s;
memset(cur, 0, sizeof(cur));
while (d[s] < n)
{
if (u == t)
{
flow += augment(s,t);
u = s;
}
bool advanced = false;
for (int i = cur[u]; i < G[u].size(); i++)
{
Edge& e = edges[G[u][i]];
if (e.cap > e.flow && d[u] == d[e.to] + 1)
{
advanced = true;
p[e.to] = G[u][i];
cur[u] = i;
u = e.to;
break;
}
}
if (!advanced) // retreat
{
int m = n - 1;
for (int i = 0; i < G[u].size(); i++)
{
Edge& e = edges[G[u][i]];
if (e.cap > e.flow)
m = min(m, d[e.to]);
}
if (--num[d[u]] == 0) break; // gap 優化
num[d[u] = m+1]++;
cur[u] = 0;
if (u != s)
u = edges[p[u]].from;
}
}
return flow;
}
} ISAP;
int main()
{
/**
#ifndef ONLINE_JUDGE
freopen("C:\\Users\\hncu_acm\\Desktop\\data.txt","r",stdin);
// freopen("out.txt","w",stdout);
#endif
*/
int T;
cin>>T;
int cas = 1;
while(T--)
{
cin>>n>>m;
ISAP.init(n);
int u,v,c;
rep(i,m)
{
scanf("%d%d%d",&u,&v,&c);
ISAP.add(u,v,c);
}
printf("Case %d: %d\n",cas++,ISAP.maxflow(1,n));
}
return 0;
}
參考連結： http://blog.csdn.net/u013480600/article/details/38796521
http://blog.csdn.net/x920405451x/article/details/39747081
http://acm.hdu.edu.cn/discuss/problem/post/reply.php?postid=31339&messageid=1&deep=0
![HDU5066-Harry And Physical Teacher Harry And Physical Teacher[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)