引用于一些大佬的文章

Dinic算法：（第二个模板为白书的写法）

poj1273为例

题意：m条路径，n个点，每条路径输入起点，终点和流量，求源点到汇点的最大流量

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#define INF 9999999
using namespace std;
int n,m;
int c[205][205],dis[205]; //c数组为原始网络
 
int BFS()
{
    queue<int>que;
    memset(dis,-1,sizeof(dis));//每次寻找增广路径都需要将dis数组重置
    dis[1]=0;   //起始点为0
    que.push(1);
    while(!que.empty())
    {
        int cur=que.front();
        que.pop();
        for(int i=1;i<=n;i++)
        {
            if(c[cur][i]&&dis[i]<0) //如果可行且该点尚未被标注
            {
                dis[i]=dis[cur]+1;  //改变dis值
                que.push(i);        //入队继续遍历
            }
        }
    }
    if(dis[n]>0) return true;  //汇点值不为-1，说明增广路径存在
    return false;              //反之不存在
}
int DFS(int point,int MAX) //point为当前遍历的节点，MAX为最大可行流量，MAX初始为INF
{
    int a;
    if(point==n) return MAX; //当前点为汇点时返回即可
    for(int i=1;i<=n;i++)
    {
        //当路径可行，对终点进行DFS
        if(c[point][i]&&dis[i]==dis[point]+1&&(a=DFS(i,min(MAX,c[point][i]))))
        {
            c[point][i]-=a; //构建残余网络
            c[i][point]+=a; //建立反向弧
            return a;
        }
    }
    return 0;
}
 
int main()
{
    while(cin>>m>>n)
    {
        memset(c,0,sizeof(c));
        while(m--) //构建原始网络
        {
            int u,v,w;
            cin>>u>>v>>w;
            c[u][v]+=w;
        }
        int sum=0;
        while(BFS()) //当增广路径存在进行DFS
        {
            int s=DFS(1,INF); //从源点出发，初始最大可行流设为无穷大
            sum+=s;  //结果加上得到的最大可行流
        }
        cout<<sum<<endl;
    }
    return 0;
}

struct edge{int to,cap,rev;};
vector <edge> G[1000];//邻接图的表示
int level[400];//顶点到源点的距离标号
int iter[400];//当前弧，在其之前的边就已经没有用了

void add_edge(int from,int to,int cap)
{
    G[from].push_back((edge){to,cap,G[to].size()});
    G[to].push_back((edge){from,0,G[from].size()-1});
}
//通过BFS计算从源点出发的距离的标号
void bfs(int s)
{
    memset(level,-1,sizeof(level));
    //fill(level,level+400,-1);
    queue<int> que;
    level[s]=0;
    que.push(s);
    while(!que.empty()){
        int v =que.front();que.pop();
        for(int i=0;i<G[v].size();i++){
            edge &e=G[v][i];
            if(e.cap>0&&level[e.to]<0){
                level[e.to]=level[v]+1;
                que.push(e.to);
            }
        }
    }
}

int dfs(int v,int t,int f)
{
    if(v==t||f==0) return f;
    for(int &i=iter[v];i<G[v].size();i++){
        edge &e=G[v][i];
        if(e.cap>0&&level[v]<level[e.to]){
            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 dinic(int s,int t)
{
    int flow=0;
    for(;;){
        bfs(s);
        if(level[t]<0) return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while((f=dfs(s,t,INF))>0){
            flow+=f;
        }
    }
    return flow;
}

Ford-Flukson算法：

poj 3281为例

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
//#include <bits/stdc++.h>
#define maxn 402
#define INF 0x3f3f3f3f
using namespace std;
bool likefood[110][110];
bool likedrink[110][110];
int N,F,D;
struct edge {int to,cap,rev;};
vector <edge> G[maxn];
bool used[maxn];
void add_edge(int from,int to,int cap)
{
    G[from].push_back((edge){to,cap,G[to].size()});
    G[to].push_back((edge){from,0,G[from].size()-1});
}
int dfs(int v,int t ,int f)
{
    if(v==t) return f;
    used[v]=true;
    for(int i=0;i<G[v].size();i++){
        edge &e=G[v][i];
        if(!used[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;
    for(;;){
        memset(used,0,sizeof(used));
        int f=dfs(s,t,INF);
        if(f==0) return flow;
        flow+=f;
    }
}
int main()
{
    scanf("%d %d %d",&N,&F,&D);
    int s=N*2+F+D,t=s+1;
    for(int e=0;e<N;e++){
        int fi,di,getf,getd;
        scanf("%d %d",&fi,&di);
        for(int h=0;h<fi;h++){
            scanf("%d",&getf);
            getf-=1;
            likefood[e][getf]=true;
        }
        for(int k=0;k<di;k++){
            scanf("%d",&getd);
            getd-=1;
            likedrink[e][getd]=true;
        }
    }
    for(int i=0;i<F;i++){
        add_edge(s,N*2+i,1);
    }
    for(int i=0;i<D;i++){
        add_edge(N*2+F+i,t,1);
    }
    for(int i=0;i<N;i++){
        add_edge(i,N+i,1);
        for(int j=0;j<F;j++){
        if(likefood[i][j]){
            add_edge(N*2+j,i,1);
        }
    }
    for(int j=0;j<D;j++){
        if(likedrink[i][j]) add_edge(N+i,N*2+F+j,1);
    }
    }
    printf("%d\n",max_flow(s,t));
    return 0;
}

EK算法：

#include <iostream>
#include <queue>
#include<string.h>
using namespace std;
#define arraysize 201
int maxData = 0x7fffffff;
int capacity[arraysize][arraysize]; //记录残留网络的容量
int flow[arraysize];                //标记从源点到当前节点实际还剩多少流量可用
int pre[arraysize];                 //标记在这条路径上当前节点的前驱,同时标记该节点是否在队列中
int n,m;
queue<int> myqueue;
int BFS(int src,int des)
{
    int i,j;
    while(!myqueue.empty())       //队列清空
        myqueue.pop();
    for(i=1;i<m+1;++i)
    {
        pre[i]=-1;
    }
    pre[src]=0;
    flow[src]= maxData;
    myqueue.push(src);
    while(!myqueue.empty())
    {
        int index = myqueue.front();
        myqueue.pop();
        if(index == des)            //找到了增广路径
            break;
        for(i=1;i<m+1;++i)
        {
            if(i!=src && capacity[index][i]>0 && pre[i]==-1)
            {
                 pre[i] = index; //记录前驱
                 flow[i] = min(capacity[index][i],flow[index]);   //关键：迭代的找到增量
                 myqueue.push(i);
            }
        }
    }
    if(pre[des]==-1)      //残留图中不再存在增广路径
        return -1;
    else
        return flow[des];
}
int maxFlow(int src,int des)
{
    int increasement= 0;
    int sumflow = 0;
    while((increasement=BFS(src,des))!=-1)
    {
         int k = des;          //利用前驱寻找路径
         while(k!=src)
         {
              int last = pre[k];
              capacity[last][k] -= increasement; //改变正向边的容量
              capacity[k][last] += increasement; //改变反向边的容量
              k = last;
         }
         sumflow += increasement;
    }
    return sumflow;
}
int main()
{
    int i,j;
    int start,end,ci;
    while(cin>>n>>m)
    {
        memset(capacity,0,sizeof(capacity));
        memset(flow,0,sizeof(flow));
        for(i=0;i<n;++i)
        {
            cin>>start>>end>>ci;
            if(start == end)               //考虑起点终点相同的情况
               continue;
            capacity[start][end] +=ci;     //此处注意可能出现多条同一起点终点的情况
        }
        cout<<maxFlow(1,m)<<endl;
    }
    return 0;
}