网络流---最大流（Edmond-Karp算法）的学习-白红宇

网络流---最大流（Edmond-Karp算法）的学习

阅读量：4969 次

发布时间：2019-06-12

本文共 1265 字，大约阅读时间需要 4 分钟。

先上个代码，等有空补充详解

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn = 1010;const int INF = 0x3f3f3f3f;int Map[maxn][maxn];int maxflow,n,m;int pre[maxn],flow[maxn];int start,end;void init(){ maxflow=0; memset(Map,0,sizeof(Map)); memset(flow,0,sizeof(flow)); memset(pre,-1,sizeof(pre));}void input(){ int u,v,w; start=1; end=n; while(m--){ cin>>u>>v>>w; if(u==v)continue;//起点和终点不可相等 Map[u][v]+=w;//存在u和v之间有多条边 }}int bfs(){ queue
          
           q; q.push(1); pre[1]=0; flow[1]=INF; while(!q.empty()){ int u=q.front(); q.pop(); if(u==end)break; for(int i=1;i<=n;i++){ if(i!=start&&pre[i]==-1&&Map[u][i]>0){ flow[i]=min(flow[u],Map[u][i]); pre[i]=u; q.push(i); } } } if(pre[end]==-1)return -1;//如果找不到增广路，返回-1 else return flow[end];} void ek(){ int ff=0; while(1){ ff=bfs();//bfs寻找增广路 if(ff==-1)break;//如果找不到增广路，退出循环 maxflow+=ff;//加到最大流中 int k=n; while(k!=1){//利用前驱寻找路径 Map[pre[k]][k]-=ff; Map[k][pre[k]]+=ff; k=pre[k]; } memset(pre,-1,sizeof(pre));//再次初始化 memset(flow,0,sizeof(flow)); } cout<
           
            <
            
             >n>>m;//n个顶点，m条边 init();//初始化 input();//输入 ek();//ek算法流程 return 0;}/*4 51 2 51 3 52 3 52 4 53 4 5*/