首页 > 代码库 > 增广路径求解最大流
增广路径求解最大流
关于什么是最大流。我说不清楚，而且也没有别人的比喻生动。
【主要是我懒，不想画图】
算法的核心在于：找到增广路径，修改它，继续找，直到没有。
While ( findAugmentPath() ) // 判断是否有增广路 maxFlow = maxFlow + delta // 最大流增加 modifyGraph() // 对增广路进行修改End While
最近智商有点不够用。想了很久才想通findAugmentPath()函数。
利用的是BFS。
1 int i,j,u,v; 2 int flag=0; 3 for(i=0;i<n;i++) 4 { 5 queue[i]=0;//bfs算法的队列 6 visited[i]=0;//是否被访问 7 path[i]=0;//保存走过的路 8 capacity[i]=0;//最大流 9 }//初始化10 int tail=0;//tail标记此时bfs到哪个地方了11 queue[tail]=0;12 capacity[0]=inf;13 visited[0]=1;14 i=0;15 while(i<=tail)16 {17 u=queue[i];18 if(u==n-1)//如果目的点入队说明存在增广路径19 {20 flag=1;21 return capacity[n-1];22 23 }24 25 for(v=0;v<n;v++)//bfs26 {27 if(r[u][v]>0&&r[u][v]!=inf&&visited[v]==0)28 {29 //cout<<v<<endl;30 path[v]=u;31 capacity[v]=min(r[u][v],capacity[u]);32 visited[v]=true;33 tail=tail+1;34 queue[tail]=v;35 }36 37 }38 i++;39 }
我在想如果只是需要找到一条增广路径，然后修改它，dfs算法也可以。【于是给自己挖了一个坑】
对增广路径的修改，就是找到了某一个路径的最大流，然后经过的路径全部减去这个最大流，意思是下次这里不通了。
1 void modifyGraph() 2 { 3 int flow=capacity[n-1]; 4 int now=n-1; 5 while(now!=0) 6 { 7 int fa=path[now]; 8 r[fa][now]=r[fa][now]-flow; 9 // r[now][fa]=r[now][fa]+flow;10 now=fa;11 12 } 13 }
增广路径求解最大流
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。