前面的的几篇关于网络流的我被坑了，原来我用的算法叫做EK
下面总结下网络流的模板吧
1 #include <iostream> 2 #include <queue> 3 //#include <conio.h> 4 using namespace std; 5 #define arraysize 201 6 int maxData = 0x7fffffff; 7 int capacity[arraysize][arraysize]; //记录残留网络的容量 8 int flow[arraysize]; //标记从源点到当前节点实际还剩多少流量可用 9 int pre[arraysize]; //标记在这条路径上当前节点的前驱,同时标记该节点是否在队列中 10 int n,m; 11 queue<int> myqueue; 12 int BFS(int src,int des) //EK算法使用BFS寻找增广路径 13 { 14 int i,j; 15 while(!myqueue.empty()) //队列清空 16 myqueue.pop(); 17 for(i=1;i<m+1;++i) //初始化前驱 18 { 19 pre[i]=-1; 20 } 21 pre[src]=0; 22 flow[src]= maxData; //初始化源点的流量为无穷大 23 myqueue.push(src); 24 while(!myqueue.empty()) 25 { 26 int index = myqueue.front(); 27 myqueue.pop(); 28 if(index == des) //找到了增广路径 29 break; 30 for(i=1;i<m+1;++i) //遍历所有的结点 31 { 32 if(i!=src && capacity[index][i]>0 && pre[i]==-1) 33 { 34 pre[i] = index; //记录前驱 35 flow[i] = min(capacity[index][i],flow[index]); //关键：迭代的找到增量 36 myqueue.push(i); 37 } 38 } 39 } 40 if(pre[des]==-1) //残留图中不再存在增广路径 41 return -1; 42 else 43 return flow[des]; 44 } 45 int maxFlow(int src,int des) 46 { 47 int increasement= 0; 48 int sumflow = 0; 49 while((increasement=BFS(src,des))!=-1) 50 { 51 int k = des; //利用前驱寻找路径 52 while(k!=src) 53 { 54 int last = pre[k]; 55 capacity[last][k] -= increasement; //改变正向边的容量 56 capacity[k][last] += increasement; //改变反向边的容量 57 k = last; 58 } 59 sumflow += increasement; 60 } 61 return sumflow; 62 }
这个算法要好好学习下