网络最大流是图论中的一个典型问题,为了精确的定义最大流问题,先给出下面几个定义。
一、流网络:G(E,V)是一个有向图,对于G中的每一对顶点(u,v)均有一非负的容量c(u,v),如果(u,v)属于E,那么c(u,v)>0,否则c(u,v)=0.
二、流:设G(E,V)是一个流网络,那么G的流是定义在V*V上的一个实值函数f,并且满足一下三个性质:
1)容量限制:f(u,v)<=c(u,v)
2)反对称性:f(u,v)=-f(v,u)
3)流守恒性:简单点说就是:对于非源点,它流出的流量总和为0,对于非汇点,流入它的流量总和为0
那么给定一个流网络,最大流问题就是求该流网络中,原点流出的最大流量或者是流入汇点的最大流量。如何求解这个问题:要引入一下三个概念。
一、残余网络:在一个流网络中,给定一个流,那么我们可以根据这个流计算出对应的残余网络cf(u,v)=c(u,v)-f(u,v),值得注意的一点就是,如果f(u,v)为负,那么cf(u,v)就大于c(u,v)
二、增广路径:这个其实很简单,在一个残余网络中,任何一条从源点S到汇点T的路径(cf(u,v)>0)都是增广路径。一条增广路径的流量是路径中cf(u,v)中的最小值。
三、网络流的割:流网络G(E,V)的割(S,T)将流网络分解为S,T(V-S)两个部分,其中源点s属于S,汇点t属于T。于是我们定义割(S,T)的净流f(S,T)和容量c(S,T).其中f(S,T)为从S到T的流量总和减去从T到S的流量总和。而c(S,T)为从S到T的容量总和。
基于以上三个概念,有如下总要定理:
*最大流最小割定理
对于一个流网络G=(E,V),一下三个命题两两等价
1)f是G的一个最大流
2)残余网络Gf不存在增广路径
3)对于G的某个割(S,T),f=c(S,T)且c(S,T)是G的某个最小割
有了这个定理我们就可以找到解决最大流的算法。
基本的Ford-Fulkerson算法:
在残余网络中Gf中递归的寻找增广路径,直到找不到,那么此时的流f就是最大流。
分析算法的效率:递归寻找增广路径的过程中,不管是DFS还是BFS每次都是O(E)的效率(邻接表),那么一共要寻找多少次增广路径呢?次数我们暂且写成f*,那么Ford-Fulkerson算法的效率为O(E*(f*))。显然如果f*很大,算法效率很低,具体的例子见算法导论。
Edmonds-Karp算法(EK):
简单的说就是在寻找增广路径时使用BFS,可以证明f*=O(E*V/2)。
证明过程需要如下的引理:
一、对于流网络G=(V,E),如果进行EK算法,残余网络中Gf中的最短路径长度p(u,v)随着每次流的增加而单调递增。p(u,v)就是从u到v中的过程中路径的段数。u-i-j-v,p(u,v)=3
二、对于流网络G=(V,E),如果进行EK算法,对流进行增加的次数为O(EK)
对于引理二,有如下简单证明:
首先定义关键边:关键边就是当找到增广路径后,路径中的一段(u,v)为残余网络中cf值最小的一段,那么它将在残余网络中消失,因为cf(u,v)将为0.
一条边(u,v)从关键边,到消失,到再次成为关键边,p(s,v)至少增加了2,而图中共有V个节点,因此,任意一条边(u,v)最对(V-1)/2次成为关键边,那么G中共有E条边,就总共有O(EV)次成为关键边的过程,而一次关键边的过程就是一次流增加的过程。因此EK算法对流增加的次数为O(EV)
因此EK算法的复杂度为O(E^2*V)。
zoj_1734:对于多源点多汇点的问题只需认为加上单一的源点和汇点即可转化为EK
#include<iostream>
#include<cstdio>
#include<string.h>
#include<queue>
using namespace std;
const int MAXI=105;
int cap[MAXI][MAXI];
int n,np,nc,m;
int EK(int s,int t)
{
queue<int>q;
int remnant[MAXI][MAXI];
int fa[MAXI];
int path[MAXI];
int res=0;
memset(remnant,0,sizeof(remnant));
for(int i=0;i<n+2;i++)
for(int j=0;j<n+2;j++)
remnant[i][j]=cap[i][j];
while(1)
{
q.push(s);
memset(path,0,sizeof(path));
path[s]=1000000;
while(!q.empty())
{
int a=q.front();
q.pop();
for(int i=0;i<=t;i++)
{
if(path[i]==0&&remnant[a][i]>0)
{
q.push(i);
fa[i]=a;
path[i]=path[a]<remnant[a][i]?path[a]:remnant[a][i];
}
}
}
if(path[t]==0)
break;
for(int i=t;i!=s;i=fa[i])
{
remnant[fa[i]][i]-=path[t];
remnant[i][fa[i]]+=path[t];
}
res+=path[t];
}
return res;
}
int main()
{
freopen("e:\\zoj\\zoj_1734.txt","r",stdin);
while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF)
{
memset(cap,0,sizeof(cap));
int from,to,c;
while(m--)
{
scanf(" (%d,%d)%d",&from,&to,&c);
cap[from][to]=c;
}
while(np--)
{
scanf(" (%d)%d",&to,&c);
cap[n][to]=c;
}
while(nc--)
{
scanf(" (%d)%d",&from,&c);
cap[from][n+1]=c;
}
int res=EK(n,n+1);
printf("%d\n",res);
}
return 0;
}
发表评论
-
图的割点tarjan---zoj_1119
2011-10-24 23:00 1236http://acm.zju.edu.cn/on ... -
BFS与双向BFS---zoj_1505
2011-10-09 17:14 1647http://acm.zju.edu.c ... -
静态treap+线段树---zoj_2112
2011-09-29 23:06 1713http://acm.zju.edu ... -
NIM博弈游戏,SG函数---zoj_3084,zoj_2083
2011-09-23 23:00 1322Nim游戏是两个人进行的游戏有如下规则: ... -
多重背包--zoj_2156
2011-09-14 11:10 867首先介绍经典的三种背包问题,0-1背包,完全 ... -
模式串匹配---KMP
2011-08-31 20:49 1282朴素的的模式串匹配算法通常要在向前移动文本指针 ... -
八数码问题(A*&&双向BFS)---zoj_1217
2011-08-30 22:13 1673题目地址:http://acm.zju.edu.cn/onli ... -
ac自动机以及它上面的DFA
2011-08-08 23:04 2483AC自动机(Aho-Corasick)主要用 ... -
二分图最大匹配(匈牙利算法)--zoj1516,1525,2223
2011-07-20 22:36 1190二分图G(E,V)将点集合V分成两个部分L,R ... -
trie和前缀检查---zoj_2876
2011-07-13 23:03 871trie树是一种多叉树,广泛用于字典检索。如 ... -
位图bitmap
2011-07-13 21:08 916bitmap是一种广泛使用的数据结构,主要用在 ... -
LAC和RMQ的转化---zoj_3195
2011-07-12 22:35 1078我擦。。纠结了好久啊,从SF到TLE,先总结2 ... -
LAC的tarjan(离线)算法---zoj_1141
2011-07-08 17:52 1663LCA就不解释了,这里主要再次复习一下LC ... -
笛卡尔树以及treap---zoj_2243
2011-07-07 15:52 2847zoj_2243笛卡 ... -
线段染色,矩形切割,离散化---zoj_2301,zoj_1128
2011-06-24 22:32 1369染色问题:在一维坐标轴上(最右端为M),有N ... -
线段树---zoj_1610
2011-06-22 21:06 758线段树是一种二叉树的拓展,在线段树每个节点中 ... -
快速排序(qsort)
2011-06-16 17:03 782快速排序是一种高效的非稳定排序,它的基本思路 ... -
斐波那契散列
2011-06-16 16:38 3083斐波那契散列法其实是一种特殊的乘法散列,先来看乘法 ... -
强连通分支(scc)---tarjan
2011-06-15 16:17 1285本文大量 ... -
单源最短路径SPFA---zoj3146
2011-06-09 15:25 947针对Bellman-Ford算法效率比较低 ...
相关推荐
最近在acm.zju.edu.cn上通过的题目的代码,都是比较有价值的题目
zoj吐血制作,希望大家喜欢
zoj网站中多个练习的c++解答,文件名即为题目序号。经本人测试可以使用,主要为动态规划方面的问题,希望给初学者提供帮助。
这是一份ZOJ的ACM题解,包含大多数题目的AC程序,是学习算法的好东西~
zoj在线评测系统前台和后台源代码,包括比赛用的客户端源代码
ZOJ 1055 Oh, Those Achin Feet.bfs求最短路径.
zoj4041正确题解源代码,以及运行程序
acm中zoj1002的可运行C++程序
浙江大学ZOJ源码题解,按照题目类型和难易分类。
一个非常非常非常非常实用的zoj结题代码
问题:枫教授在一所大学教数学,他发现了一个函数,用于获得一个表达式的操作数的目的,函数命名op(i,e)可以描述如下:
zoj的代码实现,很好,而且很全面,全部实现。
zoj_1004.cpp 求单词字母进出栈后能形成目标串的进出方案 广度优先搜索求解
ZOJ上的一些水题,4.16浙江省程序设计竞赛的题目
zoj 2536 这个不是用贪心做的
zoj上的3607Lazier Salesgirl AC代码及一些注释。贪心算法
能AC 通过的c++代码,包括zoj1002,1091,1789
浙大acm OJ1204,自己做的,已经AC 分享一下,若有更好的算法可以教教我
浙江大学zoj题目代码,大量水题代码,齐全
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告