题目链接：

 

a.EK算法：(Edmond-Karp): 用BFS不断找增广路径，当找不到增广路径时当前流量即为最大流。

 

b.dinic算法：不断找最短路。

 

题意：现在有m个池塘(从1到m开始编号,1为源点,m为汇点),及n条水渠,给出这n条水渠所连接的池塘和所能流过的水量,求水渠中所能流过的水的最大容量.

 //一个写的特别好的博客，包括好几种求最大流的写法；

EK(Edmonds_Karp):不断找增广路径，当找不到增广路径时当前流量即为最大流。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define INF 0xfffffffint F[205][205],C[205][205];int a[205],p[205];int n,m,sum;void EK(){    queue
          
           q;//BFS找增广路 while(1) { memset(a,0,sizeof(a)); q.push(1);//原点入队 a[1]=INF; while(!q.empty()) { int u=q.front(); q.pop(); for(int v=1; v<=m; v++) { if(!a[v] && C[u][v]-F[u][v]>0) { p[v]=u; q.push(v); a[v]=min(a[u],C[u][v]-F[u][v]); } } } if(a[m]==0) break; /找不到增广路，则当前流即为最大流 sum+=a[m]; for(int i=m; i!=1; i=p[i]) { F[p[i]][i]+=a[m]; F[i][p[i]]-=a[m]; } } printf("%d\n",sum);}int main(){ int x,y,z; while(scanf("%d%d",&n,&m)==2) { memset(F,0,sizeof(F)); memset(C,0,sizeof(C)); memset(p,-1,sizeof(p)); sum=0;//记录最大流 while(n--) { scanf("%d%d%d",&x,&y,&z); C[x][y]+=z;//可能会有相同边 } EK(); } return 0;}
          
         
        
       
      
     

flow[u][v]为<u,v>流量,cap[u][v]为<u,v>容量 

a[i]表示源点s到节点i路径上的最小残留量、p[i]记录i的前驱。

反向弧的作用：

意义：前的流到a的流量，来退掉一些以往流到a的流量，是这些被退掉的流量能够通过别的路径到达汇点。

//俗话说，就是原来走3，现在走1我不在你那走了，我在你那少走点吗，能在别人那走更多。起到退回的作用，非常好理解！

空间优化的EK：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define INF 0xfffffffint C[205][205];int a[205],p[205];int n,m,sum;void EK(){    queue
         
          q;    while(1)    {        memset(a,0,sizeof(a));        a[1]=INF;        q.push(1);        while(!q.empty())        {            int u=q.front();            q.pop();            for(int v=1; v<=m; v++)            {                if(!a[v] && C[u][v]>0)                {                    p[v]=u;                    q.push(v);                    a[v]=min(a[u],C[u][v]);                }            }        }        if(a[m]==0) break;        sum+=a[m];        for(int i=m; i!=1; i=p[i])        {            C[p[i]][i]-=a[m];            C[i][p[i]]+=a[m];        }    }    printf("%d\n",sum);}int main(){    int x,y,z;    while(scanf("%d%d",&n,&m)==2)    {        sum=0;        memset(C,0,sizeof(C));        memset(p,-1,sizeof(p));        while(n--)        {            scanf("%d%d%d",&x,&y,&z);            C[x][y]+=z;        }        EK();    }    return 0;}//省掉了一个flow数组。
         
        
       
      
     

 

dinic：            https://comzyh.com/blog/archives/568/#Dinic-Code

邻接矩阵实现：

#include
     
      #include
      
       #include
       
        using namespace std;#define INF 0xfffffffint C[205][205];int dis[205];int q[2000],h,r;int n,m,sum;int BFS(){    memset(dis,-1,sizeof(dis));    dis[1]=0;    h=0;    r=1;    q[1]=1;    while(h
        
         0)  //如果没有被访问过 并且两点之间“联通”            {                dis[i]=dis[j]+1;//那么到原点的距离就加一                q[++r]=i;//队列中的第几个元素是谁            }        }    }    if(dis[m]>0) return 1; //如果可以找到原点到汇点的通路 那么即找到增广路 返回1    else return 0; //汇点的DIS小于零,表明BFS不到汇点}//Find代表一次增广,函数返回本次增广的流量,返回0表示无法增广int Find(int x,int low) //找到最小的流量{    int a=0;    if(x==m) return low; //如果当前点是汇点，返回当前增加的流量    for(int i=1; i<=m; i++)        if(C[x][i]>0 && dis[i]==dis[x]+1 && (a=Find(i,min(low,C[x][i])) ) )        {            //联通 是分成图的下一层 能到汇点            C[x][i]-=a;            C[i][x]+=a;            return a;        }    return 0;}int main(){    int x,y,z,ans;    while(scanf("%d%d",&n,&m)==2)    {        memset(C,0,sizeof(C));        while(n--)        {            scanf("%d%d%d",&x,&y,&z);            C[x][y]+=z;        }        sum=0;        while(BFS())//成功建立分图            while(ans=Find(1,INF))//成功找到增广路经                sum+=ans;        printf("%d\n",sum);    }    return 0;}
        
       
      
     

 

dinic邻接表实现：

#include 
     
      #include 
      
       #include 
       
        using namespace std;#define MAXN 210#define INF 0xfffffffstruct Edge{    int st, ed;    int c;    int next;} edge[MAXN << 1];int n, m;int s, t;int ans;int e = 0;int head[MAXN];int d[MAXN];void init(){    int i,j;    int a,b,c;    s=1;    t=m;    e=0;    ans=0;    memset(head,-1 sizeof(head));    for(i=1; i<=n;i++)    {        scanf("%d%d%d",&a,&b,&c);        edge[e].st=a;        edge[e].ed=b;        edge[e].c=c;        edge[e].next=head[a];        head[a]=e++;        edge[e].st=b;        edge[e].ed=a;        edge[e].next=head[b];        head[b]=e++;    }}int bfs(){    memset(d,-1,sizeof(d));    queue
        
          q;    d[s]=0;    q.push(s);    int i;    int cur;    while(!q.empty())    {        cur=q.front();        q.pop();        for(i=head[cur]; i!=-1; i=edge[i].next)        {            if(d[edge[i].ed]==-1 && edge[i].c > 0)            {                d[edge[i].ed]=d[cur] + 1;                q.push(edge[i].ed);            }        }    }    if(d[t]<0) return 0;    return 1;}int dinic(int x, int flow){    if(x==t) return flow;            int i,a;    for(i=head[x]; i!=-1; i=edge[i].next)    {        if(d[edge[i].ed]==d[x]+1 && edge[i].c>0 && (a=dinic(edge[i].ed, min(flow,edge[i].c))))        {            edge[i].c-=a;            edge[i^1].c+=a;            return a;        }    }    return 0;}void solve(){    while(scanf("%d%d",&n,&m)!=EOF)    {        init();        while(bfs())        {            int increment;            increment=dinic(1, INF);            ans+=increment;        }        printf("%d\n",ans);    }}int main(){#ifdef LOCAL#endif    solve();    return 0;}
        
       
      
     

SAP有个优化就是 当出现断链时，就可以直接退出，还有个优化是当前弧的优化，这两个优化只需要一句话+一个数组就解决了，相当实惠，好的ISAP执行的效率真的非常高，这个写的ISAP用的是链式前向星法表示。  （相关博客）

SPFA优化:

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define MAXN 500#define MAXE 40000#define INF 0x7ffffffflong ne,nv,tmp,s,t,index;struct Edge{    long next,pair;    long v,cap,flow;} edge[MAXE];long net[MAXN];long ISAP(){    long numb[MAXN],dist[MAXN],curedge[MAXN],pre[MAXN];    long cur_flow,max_flow,u,tmp,neck,i;    memset(dist,0,sizeof(dist));    memset(numb,0,sizeof(numb));    memset(pre,-1,sizeof(pre));    for(i=1; i<=nv ; i++)        curedge[i]=net[i];    numb[nv]=nv;    max_flow=0;    u=s;    while(dist[s]
          
           edge[curedge[i]].cap) { neck=i; cur_flow=edge[curedge[i]].cap; } } for(i=s; i!=t; i=edge[curedge[i]].v) { tmp=curedge[i]; edge[tmp].cap-=cur_flow; edge[tmp].flow+=cur_flow; tmp=edge[tmp].pair; edge[tmp].cap+=cur_flow; edge[tmp].flow-=cur_flow; } max_flow+=cur_flow; u=neck; } for(i=curedge[u]; i!=-1; i=edge[i].next) if(edge[i].cap>0 && dist[u]==dist[edge[i].v]+1) break; if(i!=-1) { curedge[u]=i; pre[edge[i].v]=u; u=edge[i].v; } else { if(0==--numb[dist[u]]) break; curedge[u]=net[u]; for(tmp=nv,i=net[u]; i!=-1; i=edge[i].next) if(edge[i].cap>0) tmp=tmp