首页 > 代码库 > 最大流最小割C++实现
最大流最小割C++实现
最大流量问题：寻找从源点到汇点的最大流量。
使用最短增益路径法（或先标记先扫描法）。这里标记意味着用两个记号来标记一个新的（为标记）的顶点：第一个标记指出从源点到被标记顶点还能增加多少流量；第二用来分别个标记指出另一个顶点的名字，就是从该顶点访问到被标记顶点的（对于源点来说这个标记可以不必指定）。方便起见，也可以为第二个标记加上“+”或“-”符号，用来分别指出该顶点是通过前向边还是后向边访问到的。因此，源点可被标记为∞，-。对于其他顶点，按照以下方法计算它的标记：
（1）如果为标记顶点j是由j到i的有向边和遍历队列中的前面顶点i相连接的，而且j具有大于0的未使用容量rij=uij-xij，其中uij为边的总容量，xij为当前正容量，那么顶点j就标记为lj，i+，其中lj=min{li，rij}。
（2）如果为标记顶点j是由j到i的有向边和遍历队列中的前面顶点i相连接的，而且j具有大于0的未使用容量xji，那么顶点j就标记为lj，i-，其中lj=min{li，xji}。
如果这种加入了标记的遍历结束于汇点，当前流量的增量就可以确定为汇点的第一个标记。我们从汇点开始，沿着第二个标记回溯到源点，来执行这一增量。在这条路径上，前向边的当前流量增加，后向边的当前流量减少。另一方面，如果遍历队列为空以后，汇点仍然没有被标记，该算法就把当前流量作为最大值返回并结束算法。
最小割
首先说明什么是割——我们可以把网络的顶点分成两个子集X和X‘，X包含源点，X‘是X的部，包含汇点。所有头在X‘，尾在X的边的集合称作割，记作C（X，X‘）或C。
割C（X，X‘）容量，记作c（X，X‘），定义为构成割的边的容量和。最小割是具有最小容量的割。
最大流-最小割定理：网络中的最大流量值等于它的最小割的容量。
在最大流为问题的最后一次迭代时，所有已标记顶点到未标记顶点的边就构成了最小割。
注：以上文字摘自《算法设计与分析基础》，（美）Anany Levitin 著，潘彦 译。
#include<iostream>#include<queue>using namespace std;const int MAX=100;const int inf=1<<30;queue<int> Q;int ShortestAugmentingPath(int n,int source,int sink,int map[][MAX],int flow[][MAX],int pre_t[]){ /* n为顶点数 ,source为源点,sink为汇点,map[][]记录对应边的最大容量，flow[][]记录对应边具有的正流量; 最后一次迭代的pre_t[]记录了最小割,pre_t[i] !=0 表示属于源点集合 */ if(source==sink) //特殊情况处理 return inf; int i,x; int visited[MAX]; //visited[i]=1表示顶点i被标记 int rest[MAX][MAX]; //rest[i][j]表示顶点i到j的未使用流量 int L[MAX]; //L[i]记录一次迭代过程中节点i的最大增量 int pre[MAX]; //pre[i]=0表示顶点i未标记,pre[i] >0 表示前向边,pre[i] < 0表示后向边 //数组初始化 memset(rest,0,sizeof(rest)); memset(visited,0,sizeof(visited)); memset(flow,0,(n+1)*sizeof(flow[0])); memset(L,0x7f,n*sizeof(L[0])); memset(pre,0,sizeof(pre)); pre[source]=source+1; //任意赋值为一个整数 while(!Q.empty()) Q.pop(); Q.push(source); //最初，源点入队 while(!Q.empty()) { visited[source]=1; //源点被标记 i=Q.front(); Q.pop(); for(x=1;x<=n;x++) //前向边 { if(i!=x&&!visited[x]&&map[i][x]!=inf) { rest[i][x]=map[i][x]-flow[i][x]; if( rest[i][x] > 0 ) { L[x]=L[i] < rest[i][x] ? L[i] : rest[i][x]; //L[x]=min(rest[i][x],L[i]) Q.push(x); visited[x]=1; pre[x]=i; } } } for(x=1;x<=n;x++) //后向边 { if(i!=x&&!visited[x]&&map[x][i]!=inf) { if(flow[x][i] > 0) { L[x]=L[i] < flow[x][i] ? L[i] : flow[x][i]; Q.push(x); visited[x]=1; pre[x]=-i; } } } for(int y=1;y<=n;y++) //记录最后一次迭代结果的标记,即为最小割 pre_t[y]=pre[y]; if(visited[sink]==1) //汇点被标记了 { x=sink; while(x!=source) //从汇点开始用第二个标记反向移动 { if(pre[x]>0) flow[i][x] += L[sink]; else flow[i][x] -= L[sink]; x=i; if(pre[i]>0 ) i=pre[i]; else i=-pre[i]; } memset(visited,0,sizeof(visited)); //擦除标记 memset(L,0x7f,n*sizeof(L[0])); while(!Q.empty()) Q.pop(); Q.push(source); //用源点对q重新初始化 memset(pre,0,sizeof(pre)); pre[source]=1; } } int maxflow=0; for(i=1; i <= n;i++) maxflow+=flow[i][sink]; return maxflow;} int main(){ int map[MAX][MAX],flow[MAX][MAX],pre[MAX]; int n,i,x,w; cout<<"输入顶点数："; while(cin>>n && n) { for(i=1;i<=n;i++) { for(x=1;x<=n;x++) map[i][x]=inf; } int m; //输入边数 cout<<"输入边数： "; cin>>m; cout<<"分别输入每个有向边的起点，终点和容量："<<endl; while(m--) { cin>>i>>x>>w; map[i][x]=w; } cout<<"最大流是："<<ShortestAugmentingPath(n,1,n,map,flow,pre)<<endl; cout<<"最小割为: 源点集合X={"; for(i=1;i<=n;i++) { if(pre[i]!=0 ) cout<<i<<" "; } cout<<"}, 汇点集合Y={"; for(i=1;i<=n;i++) { if(pre[i]==0) cout<<i<<" "; } cout<<"}"<<endl; } return 0;}