最大流最小割的c++实现
算法说明：通过上课老师的讲解结合自己的看书理解和上网查询资料，用c++实现了网络流中最大流的求解（EK）算法，其中每次搜索是否有增广路用BFS搜索以提高效率，维护两个数组pre[]和flow[]（其作用在代码中有注释），每次找到一条增广路后修改残留网络的流量值，代码如下
#include<iostream> #include<vector> #include<string> #include<cmath> #include<map> #include<queue> using namespace std; #define arraysize 8 int maxdata=1000000; int capacity[arraysize][arraysize]; //记录残留网络的容量 int flow[arraysize]; //标记从源点到当前节点最多可以流入的流量（目前自己的理解是利用动态规划最后得到本次BFS路径流入des的流 量,flow[des] int pre[arraysize]; //标记当前最短路劲上下标节点的前驱以及该节点是否在路径中（记录每一次BFS过程中的最短路径） int n,m; queue<int> now_load; //进行BFS int BFS(int source,int des) { while(!now_load.empty()) now_load.pop(); //每次进行搜索时清空队列 for(int i=1;i<=m;i++) pre[i]=-1; //重置所有顶点未入路径 pre[source]=0; flow[source]=maxdata; now_load.push(source); //这三步初始化，将源节点入队 while(!now_load.empty()) //BFS搜索 { int index=now_load.front(); now_load.pop(); if(index==des) break; for(int i=1;i<=m;i++) { if(i!=source&&capacity[index][i]>0&&pre[i]==-1) { pre[i]=index; flow[i]=min(capacity[index][i],flow[index]);//关键步骤，保证路径的可流通性，小于每一条经过边的capacity now_load.push(i); } } } if(pre[des]==-1) return -1; else return flow[des]; } int maxflow(int source,int des) { int more=0; int sumflow=0; while((more=BFS(source,des)!=-1)) { int temp=des; //利用前驱寻找路径 while(temp!=source) { int last=pre[temp]; capacity[last][temp]-=more; capacity[temp][last]+=more;//反向边增加 temp=last; } sumflow+=more; } return sumflow; } int main() { int i,j; int start,end,ci; memset(capacity,0,sizeof(capacity)); memset(flow,0,sizeof(flow)); cin>>n>>m; for(i=0;i<n;++i) { cin>>start>>end>>ci; if(start == end) //考虑起点终点相同的情况 continue; capacity[start][end] +=ci; //此处注意可能出现多条同一起点终点的情况 } cout<<endl; cout<<maxflow(1,m)<<endl; return 0; } 运行检验：将书上的数据输入得到的结果如截图所示
