hdu3549(网络流入门题-最大流的Ford-Fulkerson算法)

题目：Flow Problem

网络流深入学习请戳这里。

Ford-Fulkerson方法依赖于三种重要思想，这三个思想就是：残留网络，增广路径和割。

Ford-Fulkerson方法是一种迭代的方法。开始时，对所有的u，v∈V有f(u,v)=0，即初始状态时流的值为0。在每次迭代中，可通过寻找一条“增广路

径”来增加流值。增广路径可以看成是从源点s到汇点t之间的一条路径，沿该路径可以压入更多的流，从而增加流的值。反复进行这一过程，直至增广路

径都被找出来，根据最大流最小割定理，当不包含增广路径时，f是G中的一个最大流。

#include 
#include 
#include 
#include const int N=1005;int pre[N];       //保存增广路径上的点的前驱顶点
bool vis[N];
int map[N][N];    //残留网络容量int s,t;          //s为源点，t为汇点
int n,m;bool BFS()        //找增广路
{int i,cur;std::queueQ;memset(pre,0,sizeof(pre));memset(vis,0,sizeof(vis));vis[s]=true;    Q.push(s);while(!Q.empty()){cur=Q.front();Q.pop();if(cur==t) return true;       //如果已达到汇点t，表明已经找到一条增广路径，返回true.for(i=1;i<=n;i++){if(!vis[i]&&map[cur][i])  //只有残留容量大于0时才存在边{Q.push(i);pre[i]=cur;vis[i]=true;}}}return false;
}int Max_Flow()
{int i,ans=0;while(true){if(!BFS()) return ans;     //如果找不到增广路径就返回。int Min=999999999;for(i=t;i!=s;i=pre[i])     //通过pre[]数组查找增广路径上的边，求出残留容量的最小值。Min=std::min(Min,map[pre[i]][i]);for(i=t;i!=s;i=pre[i]){map[pre[i]][i]-=Min;map[i][pre[i]]+=Min;}ans+=Min;}
}int main()
{int T,k=1;int u,v,c;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);s=1; t=n;memset(map,0,sizeof(map));while(m--){scanf("%d%d%d",&u,&v,&c);map[u][v]+=c;}printf("Case %d: %d\n",k++,Max_Flow());}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！