首先感谢（）核心思路

一、首先是FF算法，dfs找增广路，

奉上最简模板（邻接矩阵）

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define INF 100000000using namespace std;int map[10009][10009];bool used[10009];int n,m,s,t;int dfs(int b,int e,int f){ int d; if(b==e) return f; for(int i=1;i<=n;i++) { if(map[b][i]>0&&!used[i]) { used[i]=true; d=dfs(i,e,min(f,map[b][i])); if(d>0) { map[b][i]-=d; map[i][b]+=d; return d; } } }}int maxflow(int b,int e){ int flow=0; while(1) { memset(used,false,sizeof(used)); int d=dfs(b,e,INF); if(d==0) return flow;//没有增广路了 flow+=d; } return flow;}int main(){ scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1;i<=m;i++) { int v,u,w; scanf("%d%d%d",&u,&v,&w); map[u][v]=w; } printf("%d\n",maxflow(s,t)); return 0;}
           
          
         
        
       
      
     

当然需要改为vector或者数组模拟临接链表

下面是vector

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define INF 100000000using namespace std;struct H{ int to,cap,rev;};vector 
            
              map[10009];int n,m,s,t;bool used[10009];void add(int f,int t,int c){ map[f].push_back((H){t,c,map[t].size()}); map[t].push_back((H){f,0,map[f].size()-1});}int dfs(int s1,int t1,int f){ if(s1==t1) return f; for(int i=0;i
             
              0&&!used[t2]) { used[t2]=true; int d=dfs(t2,t1,min(map[s1][i].cap,f)); if(d>0) { map[s1][i].cap-=d; map[t2][map[s1][i].rev].cap+=d; return d; } } }}int maxflow(int s1,int t1){ int flow=0; while(1) { memset(used,false,sizeof(used)); int d=dfs(s1,t1,INF); if(d==0) return flow; flow+=d; }}int main(){ scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1;i<=m;i++) { int v,u,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); } printf("%d\n",maxflow(s,t)); return 0;}
             
            
           
          
         
        
       
      
     

数组莫以邻接链表，cost[i]-=d,cost[i^1]+=d;

然而基于dfs的缺点，还是不够快，所以下面EK算法登场

二、EK算法，用bfs来找增广路

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define INF 100000000using namespace std;int n,m,s1,t1;int flow[10009];//标记从源点到当前节点实际还剩多少流量可用 struct P{ int f,id;}pre[10009];//记录前驱，同时也可以标记是否在队列中struct H{ int to,cap,rev;};vector 
            
              v[10009];void add(int f,int t,int c){ v[f].push_back((H){t,c,v[t].size()}); v[t].push_back((H){f,0,v[f].size()-1});}queue 
             
               que;int bfs(int s,int t){ while(!que.empty()) que.pop(); for(int i=1;i<=n;i++) pre[i].f=-1; pre[s].f=0; flow[s]=INF; que.push(s); while(!que.empty()) { int k=que.front(); que.pop(); if(k==t) break; for(int i=0;i
              
               0&&pre[tmp.to].f==-1) { pre[tmp.to].f=k,pre[tmp.to].id=i;//此处应注意前驱的记录和使用方法 flow[tmp.to]=min(tmp.cap,flow[k]); que.push(tmp.to); } } } return pre[t].f==-1?-1:flow[t];}int maxflow(int s,int t){ int mflow=0,d; while((d=bfs(s,t))!=-1) { mflow+=d; int k=t; while(k!=s) { int p=pre[k].f; v[p][pre[k].id].cap-=d; v[k][v[p][pre[k].id].rev].cap+=d;//利用反向边 k=p; } } return mflow;}int main(){ scanf("%d%d%d%d",&n,&m,&s1,&t1); for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); } printf("%d\n",maxflow(s1,t1)); return 0;}
              
             
            
           
          
         
        
       
      
     

也可以用数组模拟临接链表

三、第三种Dinic（以上两种的结合）

Dinic算法的基本思路:

根据残量网络计算层次图。   在层次图中使用DFS进行增广直到不存在增广路   重复以上步骤直到无法增广

层次图:分层图,以[从原点到某点的最短距离]分层的图,距离相等的为一层,(比如上图的分层为{1},{2,4},{3})

观察前面的dfs算法，对于层次相同的边，会经过多次重复运算，很浪费时间，那么，可以考虑先对原图分好层产生新的层次图，即保存了每个点的层次，注意，很多人会把这里的边的最大容量跟以前算最短路时的那个权值混淆，其实这里每个点之间的距离都可以看作单位距离，然后对新图进行dfs，这时的dfs就非常有层次感，有筛选感了，同层次的点不可能在同一跳路径中，直接排除。那么运行速度就会快很多了。

代码；

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define INF 100000000using namespace std;int dep[10009],n,m,s1,t1;struct H{ int to,cap,rev;};vector 
            
              v[10009];void add(int f,int t,int c){ v[f].push_back((H){t,c,v[t].size()}); v[t].push_back((H){f,0,v[f].size()-1});}int bfs(int s,int t){ memset(dep,-1,sizeof(dep)); queue 
             
               que; while(!que.empty()) que.pop(); que.push(s); dep[s]=0;//!!! while(!que.empty()) { int k=que.front(); que.pop(); for(int i=0;i
              
               0) { dep[tmp.to]=dep[k]+1; que.push(tmp.to); } } } return dep[t]!=-1;}int dfs(int s,int t,int f){ int d; if(s==t) return f; for(int i=0;i
               
                0&&dep[tmp.to]==dep[s]+1&&(d=dfs(tmp.to,t,min(f,tmp.cap)))) { v[s][i].cap-=d; v[tmp.to][tmp.rev].cap+=d; return d; } } return 0;}int dinic(int s,int t){ int flow=0; while(bfs(s,t)) { while(1) { int d=dfs(s,t,INF); if(d==0) break; flow+=d; } } return flow;}int main(){ scanf("%d%d%d%d",&n,&m,&s1,&t1); for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); } printf("%d\n",dinic(s1,t1)); return 0;}