题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1532
题目给出源点和漏点，还有一些边，要求源与漏之间的最大流，我采用了Edmonds Karp算法，该算法是Ford-Fulkerson算法的一种实现，该算法的关键技术是残留网络和残留网络上的反向边，相当于给了搜索策略一个“反悔”的机会，算法的实行过程是每次都寻找一条源点到漏点的增广路径，算出流的大小，每次寻找到一条路径就进行累加直到无法寻找到一条增广路径。寻找增广路径的一般做法是bfs，用dfs的话迭代的次数可能会非常大，十分消耗速度。在Edmonds Karp算法中，一次增广路径的查找需要消耗O(|E|)的时间，在O(|V||E|)次增广之后最大流就能被找到，所以Edmonds Karp 算法的时间复杂度大约是O(|V||E|^2)，复杂度在边多的情况下是非常高的，还有其他如Dinic、ISAP算法等最大流算法，本次我先自写一个EdmondsKarp算法。
代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
#define pf printf
#define mem(a,b) memset(a,b,sizeof(a))
#define prime1 1e9+7
#define prime2 1e9+9
#define pi 3.14159265
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define scand(x) scanf("%llf",&x)
#define f(i,a,b) for(int i=a;i<=b;i++)
#define scan(a) scanf("%d",&a)
#define mp(a,b) make_pair((a),(b))
#define P pair<int,int>
#define dbg(args) cout<<#args<<":"<<args<<endl;
#define inf 0x3f3f3f3f
const int maxn=;
int n,m,t;
inline int read(){
int ans=,w=;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-;ch=getchar();}
while(isdigit(ch))ans=(ans<<)+(ans<<)+ch-'',ch=getchar();
return ans*w;
}
int g[maxn][maxn],pre[maxn];//这里的g数组不但保存了正向边的信息还保存了残留网络的信息
int bfs(int src,int sink)
{
int flow[maxn];
mem(pre,-);
flow[src]=inf;pre[src]=;//每次从源点发出一股无穷大的水流
queue<int> q;q.push(src);
while(!q.empty())
{
int u=q.front();
q.pop();
if(u==sink)break;//到达漏点
f(i,,n)
{
if(i!=src&&pre[i]==-&&g[u][i]>)//找到一个不是源点而且没有访问过并且与当前点存在边的结点
{
pre[i]=u;
q.push(i);
flow[i]=min(flow[u],g[u][i]);//经过i点之后的源的大小更新成为边的大小或者是前驱结点的较小值
}
}
}
if(pre[sink]==-)return -;//漏点没有被搜索到
return flow[sink];
}
int maxflow(int src,int sink)
{
int Maxflow=;
while()
{
int flow=bfs(src,sink);
if(flow==-)break;
int cur=sink;//从漏点开始，一步步向源点回退，更新残余网络
while(cur!=src)
{
int father=pre[cur];
g[father][cur]-=flow;//从父结点到当前结点的路径上的流量减少flow
g[cur][father]+=flow;//从当前结点到父结点之间增加了一条残余流量
cur=father;//回溯更新参与网络
}
Maxflow+=flow;
}
return Maxflow;
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
std::ios::sync_with_stdio(false);
while(scanf("%d%d",&m,&n)!=EOF)
{
mem(g,);
int u,v,w;
f(i,,m)
{
u=read(),v=read(),w=read();
g[u][v]+=w;
}
pf("%d\n",maxflow(,n));
} }