我们知道。增广路径EK时间是在充电算法的O（n*m^2）。找到最短增广路径的时间复杂度为O（m*n^2）。这样的时间复杂度主要是寻找扩充道路。

这里也有一个演示Dinci算法，使用BFS层次结构图，然后DFS增强。

板

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define Del(a,b) memset(a,b,sizeof(a))const int N = 1000;const int INF = 0x3f3f3f3f;struct Edge{ int from,to,cap,flow;};struct Dinic{ int n,m,s,t; vector
            
              edges; vector
             
               G[N]; bool vis[N]; int d[N],cur[N]; void init(int n) { this->n=n; for(int i=0;i<=n;i++)G[i].clear(); edges.clear(); } void AddEdge(int from,int to,int cap){ //建边 edges.push_back((Edge){from,to,cap,0}); edges.push_back((Edge){to,from,0,0}); m=edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BFS() { Del(vis,0); queue
              
                q; q.push(s); d[s]=0; vis[s]=1; while(!q.empty()) { int x=q.front();q.pop(); for(int i=0;i
               
                e.flow) { vis[e.to]=1; 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
                
                 0) { e.flow+=f; edges[G[x][i]^1].flow -= f; flow+=f; a-=f; if(a==0) break; } } return flow; } int max_flow(int s,int t) { this->s=s;this->t=t; int flow=0; while(BFS()) { Del(cur,0); flow+=DFS(s,INF); } return flow; }};Dinic solve;int main(){ int n,m; while(~scanf("%d%d",&m,&n)) { solve.init(n); for(int i=0; i
                
               
              
             
            
           
          
         
        
       
      
     

版权声明：本文博客原创文章。博客，未经同意，不得转载。