网络流基本概念
在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流，等等。50年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”，是网络应用的重要组成部分。在最近的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已不是什么稀罕的事了。本节着重介绍最大流(包括最小费用)算法，并通过实际例子，讨论如何在问题的原型上建立—个网络流模型，然后用最大流算法高效地解决问题。
1.问题描述如图5-1所示是联结某产品地v1和销售地v4的交通网，每一弧(vi,vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数表示这条运输线的最大通过能力。产品经过交通网从v1到v4。现在要求制定一个运输方案使从v1到v4的产品数量最多。
图5-1 图5-2 2.网络与网络流
给一个有向图N=(V，E)，在V中指定一点，称为源点(记为vs，和另一点，称为汇点(记为vt)，其余的点叫中间点，对于E中每条弧(vi，vj)都对应一个正整数c(vi，vj)≥O(或简写成cij)，称为f的容量，则赋权有向图N=(V，E，c，vs，vt)称为一个网络。如图5-1所给出的一个赋权有向图N就是一个网络，指定v1是源点，v4为汇点，弧旁的数字为cij。所谓网络上的流，是指
定义在弧集合E上一个函数f={f(vi，vj)}，并称f(vi，vj)为弧(vi，vj)上的流量(下面简记为fij)。如图5-2所示的网络N，弧上两个数，第一个数表示容量cij，第二个数表示流量fij。
3.可行流与最大流
在运输网络的实际问题中，我们可以看出，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0，源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。因此有：
(1)容量约束：0≤f ij≤c ij，(v i,v j)∈E，
(2)守恒条件
对于中间点：流入量=流出量；对于源点与汇点：源点的净流出量v s(f)=汇点的净流入量（-v t(f)）
的流f，称为网络N上的可行流，并将源点s的净流量称为流f的流值v(f)。
网络N中流值最大的流f*称为N的最大流。
4.可增广路径
所谓可增广路径，是指这条路径上的流可以修改，通过修改，使得整个网络的流值增大。
设f是一个可行流，P是从源点s到汇点t的一条路，若p满足下列条件：
(1)在p上的所有前向弧(vi→vj)都是非饱和弧，即0≤f ij (2)在p上的所有后向弧(vi←vj)都是非零弧，即0 则称p为(关于可行流f的)一条可增广路径。 5.最大流定理 当且仅当不存在关于f*的增广路径，可行流f*为最大流。 5. 2 最大流算法 算法思想:最大流问题实际上是求一可行流{fij}，使得v(f)达到最大。若给了一个可行流f，只要判断N中有无关于f的增广路径，如果有增广路径，改进f，得到一个流量增大的新的可行流；如果没有增广路径，则得到最大流。 1.寻求最大流的标号法(Ford,Fulkerson) 从一个可行流(一般取零流)开始，不断进行以下的标号过程与调整过程，直到找不到关于f的可增广路径为止。 (1)标号过程 在这个过程中，网络中的点分为已标号点和未标号点，已标号点又分为已检查和未检查两种。每个标号点的标号信息表示两个部分：第一标号表明它的标号从哪一点得到的，以便从vt开始反向追踪找出也增广路径；第二标号是为了表示该顶点是否已检查过。 标号开始时，给vs标上(s，0)，这时vs是标号但末检查的点，其余都是未标号的点，记为(0，0)。 取一个标号而未检查的点vi，对于一切未标号的点vj： A．对于弧(vi，vj)，若fij B．对于弧(vi，vj)，若fji>0，则给vj标号(-vi，0)，这时，vj点成为标号而未检查的点。 于是vi成为标号且已检查的点，将它的第二个标号记为1。重复上述步骤，一旦vt被标上号，表明得到一条从vi到vt的增广路径p，转入调整过程。 若所有标号都已检查过去，而标号过程进行不下去时，则算法结束，这时的可行流就是最大流。 (2)调整过程 从vt点开始，通过每个点的第一个标号，反向追踪，可找出增广路径P。例如设vt的第一标号为vk(或-vk)，则弧(vk，vt)(或相应地(vt，vk))是p上弧。接下来检查vk的第一标号，若为vi(或-vi)，则找到(vi，vk)(或相应地(vk，vi))。再检查vi的第一标号，依此类推，直到vs为止。这时整个增广路径就找到了。在上述找增广路径的同时计算Q： Q=min{min(cij-fij)，minf*ij} 对流f进行如下的修改： f'ij = fij+Q (vi，vj)∈ P的前向弧的集合 f'ij = fij-Q (vi，vj)∈ P的后向弧的集合 f'ij = f*ij (vi，vj)不属于P的集合 接着，清除所有标号，对新的可行流f’，重新进入标号过程。 Codevs 1993 草地排水 题目描述Description 在农夫约翰的农场上，每逢下雨，Bessie最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了，并且小草要继续生长还要花相当长一段时间。因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心，雨水会流向附近的一条小溪）。作为一名一流的技师，农夫约翰已经在每条排水沟的一端安上了控制器，这样他可以控制流入排水沟的水流量。 农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网）。需要注意的是，有些时候从一处到另一处不只有一条排水沟。 根据这些信息，计算从水潭排水到小溪的最大流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形。 输入描述Input Description 第1行: 两个用空格分开的整数N (0 <= N <= 200) 和M (2 <= M <= 200)。N是农夫John已经挖好的排水沟的数量，M是排水沟交叉点的数量。交点1是水潭，交点M是小溪。 第二行到第N+1行: 每行有三个整数，Si, Ei, 和Ci。Si 和Ei (1 <= Si, Ei <= M) 指明排水沟两端的交点，雨水从Si 流向Ei。Ci (0 <= Ci <= 10,000,000)是这条排水沟的最大容量。 输出描述Output Description 输出一个整数，即排水的最大流量。 样例输入Sample Input 5 4 1 2 40 1 4 20 2 4 20 2 3 30 3 4 10 样例输出Sample Output 50 Dinic算法: #include #include #include #include #include using namespace std; const int mn=22222; const int mm=1000000+5; const int inf=0x3fffffff;//1073741823 int n,m, st, sd, cnt; int dis[mn], que[mn],work[mn]; int ans; struct data { int to; int flow; int next; int head; }e[mm]; void init() { st=1;sd=n; for(int i=1; i<=n; i++) { e[i].head=0; } cnt=0; } void addedge(int u, int v, int c) { cnt++; e[cnt].to=v; e[cnt].flow=c; e[cnt].next=e[u].head; e[u].head=cnt; } bool bfs() { int u, v, l=1, h=0; for(int i=1; i<=n; i++) dis[i]=-1; que[1]=st; dis[st]=0; while(l { h++; u=que[h]; for(int i=e[u].head;i>0;i=e[i].next) { v=e[i].to; if(e[i].flow&&dis[v]<0) { dis[v]=dis[u]+1; l++; que[l]=v; if(v==sd) return true; } } } return false; } int dfs(int u, int exp) { if(u==sd) return exp; for(int i=work[u]; i>0; i=e[i].next) { int v=e[i].to,tp; if(e[i].flow&&dis[v]==dis[u]+1&&(tp=dfs(v,min(e[i].flow,exp)))>0) { e[i].flow-=tp; e[i+1].flow+=tp; return tp; } } return 0; } void Dinic() { while(bfs()) { for(int i=0; i while(dfs(st,inf)); } } int main() { scanf("%d%d",&m,&n); init(); for(int i=1; i<=m; i++) { int u, v, w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,0); } Dinic(); ans=0; for(int i=e[sd].head; i>0; i=e[i].next) { int v=e[i].to; ans+=e[i].flow; } printf("%d\n",ans); return 0; } SAP算法: #include #include #include #include using namespace std; #define MAXN 444 //邻接表要开边数的2倍 struct Edge{ int v,cap,next; }edge[MAXN]; int level[MAXN];//标记层次（距离标号） //间隙优化，定义gap[i]为标号是i的点的个数 //在重标记i时，检查gap[level[i]],若减为0,这算法结束。int gap[MAXN]; int pre[MAXN];//前驱 int cur[MAXN]; int head[MAXN]; int NV,NE; //NE为边数，初始化为0； void Insert(int u,int v,int cap,int cc=0){ edge[NE].cap=cap;edge[NE].v=v; edge[NE].next=head[u];head[u]=NE++; edge[NE].cap=cc;edge[NE].v=u; edge[NE].next=head[v];head[v]=NE++; } //参数，源点，汇点 int SAP(int vs,int vt){ memset(level,0,sizeof(level)); memset(pre,-1,sizeof(pre)); memset(gap,0,sizeof(gap)); //cur[i]保存的是当前弧 for(int i=0;i<=NV;i++)cur[i]=head[i]; int u=pre[vs]=vs;//源点的pre还是其本身 int maxflow=0,aug=-1; gap[0]=NV; while(level[vs] loop : for(int &i=cur[u];i!=-1;i=edge[i].next){ int v=edge[i].v;//v是u的后继 //寻找可行弧 if(edge[i].cap&&level[u]==level[v]+1){ //aug表示增广路的可改进量 aug==-1?(aug=edge[i].cap):(aug=min(aug,edge[i].cap)); pre[v]=u; u=v; //如果找到一条增广路 if(v==vt){ maxflow+=aug;//更新最大流； //路径回溯更新残留网络 for(u=pre[v];v!=vs;v=u,u=pre[u]){ //前向弧容量减少，反向弧容量增加 edge[cur[u]].cap-=aug; edge[cur[u]^1].cap+=aug; } aug=-1; } goto loop; } } int minlevel=NV; //寻找与当前点相连接的点中最小的距离标号（重标号） for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(edge[i].cap&&minlevel>level[v]){ cur[u]=i;//保存弧 minlevel=level[v]; } } if((--gap[level[u]])==0)break;//更新gap数组后如果出现断层，则直接退出。 level[u]=minlevel+1;//重标号 gap[level[u]]++;//距离标号为level[u]的点的个数+1; u=pre[u];//转当前点的前驱节点继续寻找可行弧 } return maxflow; } int main(){ int m;//边的条数 while(~scanf("%d%d",&m,&NV)){ memset(head,-1,sizeof(head)); NE=0; for(int i=1;i<=m;i++){ int u,v,cap; scanf("%d%d%d",&u,&v,&cap); Insert(u,v,cap); } printf("%d\n",SAP(1,NV)); } return 0; } Codevs 1914 运输问题 题目描述Description W 公司有m个仓库和n 个零售商店。第i 个仓库有ai 个单位的货物；第j 个零售商店 需要bj个单位的货物。货物供需平衡，即sum(si）=sum(bj) 。从第i 个仓库运送每单位货物到 第j 个零售商店的费用为cij 。试设计一个将仓库中所有货物运送到零售商店的运输方案， 使总运输费用最少。 编程任务： 对于给定的m 个仓库和n 个零售商店间运送货物的费用，计算最优运输方案和最差运输方案。 输入描述Input Description 的第1行有2 个正整数m和n，分别表示仓库数和 零售商店数。接下来的一行中有m个正整数ai ，1≤i≤m，表示第i个仓库有ai 个单位的货 物。再接下来的一行中有n个正整数bj ，1≤j≤n，表示第j个零售商店需要bj 个单位的货 物。接下来的m行，每行有n个整数，表示从第i 个仓库运送每单位货物到第j个零售商店 的费用cij 。 输出描述Output Description 将计算出的最少运输费用和最多运输费用输出 样例输入Sample Input 2 3 220 280 170 120 210 77 39 105 150 186 122 样例输出Sample Output 48500 69140 把所有仓库看做二分图中顶点Xi，所有零售商店看做二分图中顶点Yi，建立附加源S汇T。 1、从S向每个Xi连一条容量为仓库中货物数量ai，费用为0的有向边。 2、从每个Yi向T连一条容量为商店所需货物数量bi，费用为0的有向边。 3、从每个Xi向每个Yj连接一条容量为无穷大，费用为cij的有向边。 这道题其实就是求一个网络中的最小费用最大流和最大费用最大流，最小费用最大流略过，最大费用最大流有2中方法： 1、把所有费用变成相反数做一遍最小费用最大流，输出答案的相反数； 2、初始化spfa时dis数组全从max改为-1，松弛的条件从dis[i]>dis[j]+cap[i,j]改为dis[i] #include #include 网络流算法 在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流，等等。50年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”，是网络应用的重要组成部分。在最近的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已不是什么稀罕的事了。本节着重介绍最大流(包括最小费用)算法，并通过实际例子，讨论如何在问题的原型上建立—个网络流模型，然后用最大流算法高效地解决问题。 ［问题描述］如图4-1所示是联结某产品地v1和销售地v4的交通网，每一弧(vi,vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数表示这条运输线的最大通过能力。产品经过交通网从v1到v4。现在要求制定一个运输方案使从v1到v4的产品数量最多。 一、基本概念及相关定理 1)网络与网络流 定义1 给一个有向图N=(V，E)，在V中指定一点，称为源点(记为vs，和另一点，称为汇点(记为vt)，其余的点叫中间点， 对于E中每条弧(vi，vj)都对应一个正整数c(vi，vj)≥O(或简写成cij)，称为f的容量，则赋权有向图N=(V，E，c，vs，vt)称为一个网络。如图4-1所给出的一个赋权有向图N就是一个网络，指定v1是源点，v4为汇点，弧旁的数字为cij。 所谓网络上的流，是指定义在弧集合E上一个函数f={f(vi，vj)}，并称f(vi，vj)为弧(vi，vj)上的流量(下面简记为fij)。如图4-2所示的网络N，弧上两个数，第一个数表示容量cij，第二个数表示流量fij。 2)可行流与最大流 在运输网络的实际问题中，我们可以看出，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0，源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。因此有： 定义2 满足下列条件 (1)容量约束：0≤fij≤cij，(vi,vj)∈E， (2)守恒条件 对于中间点：流入量=流出量；对于源点与汇点：源点的净流出量vs(f)=汇点的净流入量（-vt(f)）的流f，称为网络N上的可行流，并将源点s的净流量称为流f的流值v(f)。 网络N中流值最大的流f*称为N的最大流。 3)可增广路径 所谓可增广路径，是指这条路径上的流可以修改，通过修改，使得整个网络的流值增大。 定义3 设f是一个可行流，P是从源点s到汇点t的一条路，若p满足下列条件： 给定一个有向图D=(V,A)，在V中指定一点称为发点（记为），该点只有出发去的弧，指定另一点称为收点（记为），该点只有指向它的弧，其余的点叫做中间点。对于A中的每一条弧，对应一个数（简记），称之为弧的容量。通常我们把这样的D叫做网络，记为D=(V,A,C)。 （2）网络流：在弧集A上定义一个非负函数。是通过弧的实际流量，简记，称是网络上的流函数，简称网络流或流，称为网络流的流量。 §4 网络最大流问题 网络最大流问题是网络的另一个基本问题。 许多系统包含了流量问题。例如交通系统有车流量，金融系统有现金流，控制系统有信息流等。许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。 4.1 基本概念与定理 1．1．网络与流 定义14 （1）网络： 例1如图7-20是连结某产品产地和销地的交通图。弧表示从 到的运输线，弧旁的数字表示这条运输线的最大通过能力，括号内的数字表示该弧上的实际流。现要求制定一个运输方案，使从运到的产品数量最多。 可行流与最大流 在运输网络的实际问题中，我们可以看出，对于流有两个基本要求： 一是每条弧上的流量必须是非负的且不能超过该弧的最大通过能力（即该弧的容量）； 二是起点发出的流的总和（称为流量），必须等于终点接收的流的总和，且各中间点流入的流量之和必须等于从该点流出的流量之和，即流入的流量之和与流出的流量之和的差为零，也就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。 因此有下面所谓的可行流的定义。 定义14对于给定的网络D=（V,A,C）和给定的流，若满足下列条件： （1）容量限制条件：对每一条弧，有 (7.9) （2）平衡条件： 对于中间点： 流出量=流入量，即对于每一个i (i≠s,t)，有 (7.10) 对于出发带点，有 (7.11) 对于收点，有 (7.12) 则称为一个可行流，称为这个可行流的流量。 注意，我们这里所说的出发点是指只有从发出去的弧，而没有指向的弧； 收点是指只有弧指向，而没有从它的发出去的弧。 从一道题目的解法试谈网络流的构造与算法 福建师大附中江鹏 1. 引论 A. 对网络流算法的认识 网络流算法是一种高效实用的算法，相对于其它图论算法来说，模型更加复杂，编程复杂度也更高，但是它综合了图论中的其它一些算法（如最短路径），因而适用范围也更广，经常能够很好地解决一些搜索与动态规划无法解决的，看似NP的问题。 B. 具体问题的应用 网络流在具体问题中的应用，最具挑战性的部分是模型的构造。这没用现成的模式可以套用，需要对各种网络流的性质了如指掌（比如点有容量、容量有上下限、多重边等等），并且归纳总结一些经验，发挥我们的创造性。 2. 例题分析 【问题1】项目发展规划（Develop） Macrosoft?公司准备制定一份未来的发展规划。公司各部门提出的发展项目汇总成了一张规划表，该表包含了许多项目。对于每个项目，规划表中都给出了它所需的投资或预计的盈利。由于某些项目的实施必须依赖于其它项目的开发成果，所以如果要实施这个项目的话，它所依赖的项目也是必不可少的。现在请你担任Macrosoft?公司的总裁，从这些项目中挑选出一部分，使你的公司获得最大的净利润。 ●输入 输入文件包括项目的数量N，每个项目的预算Ci和它所依赖的项目集合Pi。格式如下：第1行是N； 接下来的第i行每行表示第i个项目的信息。每行的第一个数是Ci，正数表示盈利，负数表示投资。剩下的数是项目i所依赖的项目的编号。 每行相邻的两个数之间用一个或多个空格隔开。 ●输出 第1行是公司的最大净利润。接着是获得最大净利润的项目选择方案。若有多个方案，则输出挑选项目最少的一个方案。每行一个数，表示选择的项目的编号，所有项目按从小到大的顺序输出。 ●数据限制 0≤Ｎ≤1000 -1000000≤Ci≤1000000 ●输入输出范例 1．下列流类中可以用于处理文件的是（）。Empty! (D) (a) ios (b) iostream (c) strstream (d) fstream 2．在下列选项中（）是istream类的对象。Empty! (B) (a) cerr (b) cin (c) clog (d) cout 3．read函数的功能是从输入流中读取（）。Empty! (D) (a) 一个字符(b) 当前字符(c) 一行字符(d) 指定若干个字节 4．下列选项中，用于清除基数格式位设置以十六进制输出的语句是（）。Empty! (B) (a) cout << setf( ios::dec, ios::basefield ) ; (b) cout << setf( ios::hex, ios::basefield ) ; (c) cout << setf( ios::oct, ios::basefield ) ; (d) cin >> setf( ios::hex, ios::basefield ) ; 5．下列格式控制符，既可以用于输入，又可以用于输出的是（）。Empty! (A) (a) setbase (b) setfill (c) setprecision (d) setw 6．下列串流类，在strstream.h中定义的是（）。Empty! (B) (a) istringstream (b) istrstream (c) ostringstream (d) stringstream 7．包含类fstream定义的头文件是（）。Empty! (A) (a) fstream.h (b) ofstream.h (c) ifstream.h (d) iostream.h 8．要求打开文件 D:\file.dat，并能够写入数据，正确的语句是（）。Empty! (D) (a) ifstream infile( "D:\\file.dat", ios::in ) ; (b) ifstream infile( "D:\\file.dat", ios::out ) ; (c) ofstream outfile( "D:\\file.dat", ios::in ) ; 网络流模型总结 福州一中肖汉骏【引言】： “许多问题可以先转化为网络流问题，再运用最大流算法加以解决。而发现问题本质，根据最大流算法的特点，设计与之相配的数学模型是运用最大流算法解决问题的重要步骤。” “网络流在具体问题中的应用，最具挑战性的部分是模型的构造。这没用现成的模式可以套用，需要对各种网络流的性质了如指掌（比如点有容量、容量有上下限、多重边等等），并且归纳总结一些经验，发挥我们的创造性。” 注：本文大部分出自江涛老师讲稿及网络资料 图1.1 【理论部分】： 一、引入 如同我们可以把一个实际的道路地图抽象成一个有向图来计算两点之间的最短路径，我们也可以将一个有向图看作一个流网络来解决另一类型的问题。流网络比较适合用来模拟液体流经管道、电流在电路网络中的运动、信息网络中信息的传递等等类似的过程。 一个实例：运输网络 参看下图，给定一个有向图G=(V ,E)，把图中的边看作管道，每条边上有一个权值，表示该管道的流量上限。给定源点s 和汇点t ，现在假设在s 处有一个水源，t 处有一个蓄水池，问从s 到t 的最大水流量是多少，类似于这类的问题都可归结为网络流问题。 在流网络中，每条有向边可以被看导管。每根导管有一个固定的容量，代表物质流经这个导管的最大速率，例如一个管道每小时最多能流过200加仑液体或者一根电线最多能承载20安培的电流。流网络中的顶点可以看作是导管的连接处。除了源点和汇点之外，物质流进每个点的速率必须等于流出这个点的速率。如果我们把研究的物质特化为电流，这种“流的保持”属性就好像电路中的基尔霍夫电流定律一样。 二、网络流相关定义1 网络定义： 一个有向图 G=(V ，E)； 有两个特别的点：源点s 、汇点t ； 图中每条边(u,v)∈E ，有一个非负值的容量C(u,v) 记为 G=(V ，E ，C)，网络三要素：点、边、容量 可行流定义： 是网络G 上的一个“流”，即每条边上有个“流量”P(u,v)，要满足下面两个条件： 流的容量限制——弧： ),(),(0v u C v u P ≤≤ 对任意弧(u,v)---有向边 流的平衡限制——点： 除源点和汇点，对任意中间点有：流入u 的“流量”与流出u 的“流量”相等。即： {,}(,)(,)0x V x V u V s t P x u P u x ∈∈?∈--=∑∑有 网络的割： 一个s-t 割是这样一个边的集合，把这些边从网络中删除之后，s 到t 就不可达了。或者，正式的说，一个割把顶点集合分成A,B 两个集合，其中s 在A 中,t 在B 中，而割中的边就是所有从A 出发，到达B 的所有边。 割的容量就是割中所有边的容量的和。正式的说，就是所有从A 到B 的边的容量的和。 网络的流量： 源点的净流出“流量” 或 汇点的净流入“流量”。即： ∑∑∑∑∈∈∈∈-=-V x V x V x V x x t P t x P s x P x s P ),(),(),(),( 注意，我们这里说的流量是一种速率，而不是指总量。联系上面所说的实例，下面是一个流量为1的可行流： 网络流常用算法： 1.Fort_Fulkerson算法. 2.Edmonds_Karp算法(最短增广路算法).-------------------O( n*m^2 ) 3.SAP算法(使用距离标号的最短增广路算法).--------------O( n^2*m ) 4.Dinic算法.------------------------------------------O( n^2*m ) 5.Push_Relabel算法(预流推进算法).---------------------O( n^2*m ) 6.FIFO Preflow_Push算法.-------------------------------O( n^2*m) 7.Relabel_to_Front算法.--------------------------------O( n^3 ) 8.Highest Label Preflow_push算法.----------------------O( n^2*m^1/2) 网络流算法讲座材料 1 概念与性质 网络N是指具有以下结构的有向图D，D中有两个称为源和汇的不同顶点s, t，在D的弧集E上定义了非负整数值函数c。 网络N的流是定义在弧集E上的整数值函数，满足对任意边a， 0<=f(a)<=c(a)，且对任意顶点，入流量等于出流量。 性质1：任何st-流都具有如下性质：从s的出流量等于到t的入流量。 性质2：任何st-流都有一个最大流，它可以表示为从s到t，至多E条有向路径集合上的流。 图的切割是将顶点分成两个独立的集合，交叉边是一条连通两个集合中顶点的边，交叉边的集合叫做切割集合。 网络N的st-切割是这样的一个切割，它将源s放到一个集合，将汇t放到另一个集合。与st-切割对应的每条交叉边或者是st-边(从集合s指向集合t)，或者是ts-边(从集合t指向集合s)，st-切割的容量是st-边的容量之和，st-切割的流量等于st-边上的流量和与ts-边上的流量和之差。 性质3：网络中所有st-流的最大值等于所有st-切割的最小容量。 残余网络 边费用是定义在边集E上的整数值函数h。流的费用是该流的所有边的流值与边费用乘积的总和。 最小费用最大流是费用最小的最大流。 性质4：当且仅当残余网络不包含负开销的有向环时，最大流才是一个最小费用流。 2 最大流应用 2.1 一般网络的最大流 描述：给定一个含多个源和多个汇的网络，找出其中的最大流。 解法：在原网络的基础上，增加一个虚源s和一个虚汇t。若原网络有p个源s1, s2, …, sp和q个汇t1, t2, …, tq，则在原网络中增加p条以s为起 (2010-02-07 18:00:40) 转载 分类：ACM 标签： 杂谈 最大流 POJ 1273 Drainage Ditches POJ 1274 The Perfect Stall (二分图匹配) POJ 1698 Alice's Chance POJ 1459 Power Network POJ 2112 Optimal Milking (二分) POJ 2455 Secret Milking Machine (二分) POJ 3189 Steady Cow Assignment (枚举) POJ 1637 Sightseeing tour (混合图欧拉回路) POJ 3498 March of the Penguins (枚举汇点) POJ 1087 A Plug for UNIX POJ 1149 Pigs (构图题) ZOJ 2760 How Many Shortest Path (边不相交最短路的条数) POJ 2391 Ombrophobic Bovines (必须拆点，否则有BUG) WHU 1124 Football Coach (构图题) SGU 326 Perspective (构图题，类似于 WHU 1124) UVa 563 Crimewave UVa 820 Internet Bandwidth POJ 3281 Dining (构图题) POJ 3436 ACM Computer Factory POJ 2289 Jamie's Contact Groups (二分) SGU 438 The Glorious Karlutka River =) (按时间拆点) SGU 242 Student's Morning (输出一组解) SGU 185 Two shortest (Dijkstra 预处理，两次增广，必须用邻接阵实现，否则 MLE) HOJ 2816 Power Line POJ 2699 The Maximum Number of Strong Kings (枚举+构图) 第10章异常测试题2010-12-11 一、选择题 1.假设文件中的信息为abcd,下面代码执行的结果是什么: public static void main(String[]args)throws IOException{ FileInputStream fis=new FileInputStream("a.txt"); int data=fis.read(); System.out.println(data); fis.close();//a的ASCII码为97，A的为65 } A.97 B.a C.-1 D.编译出错 E.运行出错 2.假设文件中的信息为abcd,下面代码执行的结果是什么: public static void main(String[]args)throws Exception{ FileInputStream fis=new FileInputStream("a.txt"); int data=fis.readInt(); System.out.println(data); fis.close(); } A.97 B.a C.-1 D.编译出错 E.运行出错 3.下面程序执行的结果是什么: public static void main(String[]args)throws IOException{ //TODO Auto-generated method stub FileOutputStream fos=new FileOutputStream("a.txt"); fos.write Int(97); fos.close(); } A.文件中写入97 B.文件中写入a C.文件中写入-1 D.编译出错 E.运行出错 4.下面程序执行的结果是什么: public static void main(String[]args)throws IOException{ FileOutputStream fos=new FileOutputStream("a.txt"); fos.write(97); } A.文件中写入97 B.文件中写入a C.文件中写入-1 D.编译出错 E.运行出错 5.下面程序执行的结果是什么: public static void main(String[]args)throws IOException{ BufferedOutputStream fos=new BufferedOutputStream("a.txt"); fos.write(97); 浅谈网络流算法与几种流模型 吴迪1314010425 摘要：最大流的算法,算法思想很简单,从零流开始不断增加流量，保持每次增加流量后都满足容量限制、斜对称性和流量平衡3个条件。只要残量网络中不存在增广路，流量就可以增大，可以证明他的逆命题也成立；如果残量网络中不存在增广路，则当前流就是最大流。这就是著名的增广路定理。s-t的最大流等于s-t的最小割，最大流最小割定理。网络流在计算机程序设计上有着重要的地位。 关键词：网络流Edmonds-Karp 最大流 dinic 最大流最小割网络流模型最小费用最大流 正文： 图论中的一种理论与方法，研究网络上的一类最优化问题。1955年，T.E.哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，L.R. 福特和 D.R. 富尔克森等人给出了解决这类问题的算法，从而建立了网络流理论。所谓网络或容量网络指的是一个连通的赋权有向图 D= （V、E、C），其中V 是该图的顶点集，E是有向边(即弧)集，C是弧上的容量。此外顶点集中包括一个起点和一个终点。网络上的流就是由起点流向终点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去起点和终点以外，在所有中途点要求保持流入量和流出量是平衡的。如果把下图看作一个公路网，顶点v1…v6表示6座城镇，每条边上的权数表示两城镇间的公路长度。现在要问：若从起点v1将物资运送到终点v6去，应选择那条路线才能使总运输距离最短?这样一类问题称为最短路问题。如果把上图看作一个输油管道网，v1 表示发送点，v6表示接收点，其他点表示中转站，各边的权数表示该段管道的最大输送量。现在要问怎样安排输油线路才能使从v1到v6的总运输量为最大。这样的问题称为最大流问题。 最大流理论是由福特和富尔克森于 1956 年创立的，他们指出最大流的流值等于最小割(截集)的容量这个重要的事实，并根据这一原理设计了用标号法求最大流的方法，后来又有人加以改进，使得求解最大流的方法更加丰富和完善。最大流问题的研究密切了图论和运筹学，特别是与线性规划的联系，开辟了图论应用的新途径。 先来看一个实例。 现在想将一些物资从S运抵T，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。如下： 每条弧代表一条公路，弧上的数表示该公路的最大运载量。最多能将多少货物从S运抵T？ 这是一个典型的网络流模型。为了解答此题，我们先了解网络流的有关定义和概念。 若有向图G=(V,E)满足下列条件： 1、有且仅有一个顶点S，它的入度为零，即d-(S) = 0，这个顶点S便称为源点，或称为发点。 2、有且仅有一个顶点T，它的出度为零，即d+(T) = 0，这个顶点T便称为汇点，或称为收点。 3、每一条弧都有非负数，叫做该边的容量。边(vi, vj)的容量用cij表示。 则称之为网络流图，记为G = (V, E, C) 介绍完最大流问题后，下面介绍求解最大流的算法,算法思想很简单,从零流开始不断增加流量，保持每次增加流量后都满足容量限制、斜对称性和流量平衡3个条件。 三个基本的性质: 如果C代表每条边的容量F代表每条边的流量 一个显然的实事是F小于等于C 不然水管子就爆了 这就是网络流的第一条性质容量限制(Ca pacity Constraints):F 第10章输入/输出流 10.1 选择题 1．下列类中( ac)不是输入输出流类iostream的派生类。 (a)fstream (b)ofstream (c)strstream (d)ostrstream 2．在下列选项中( d )是ostream类的对象。 (a)cin (b)cerr (c)clog (d)cout 3．read函数的功能是从输入流中读取( c )。 (a)一个字符 (b)当前字符 (c)一行字符 (d)指定若 干个字符 4．下列选项中，用于清除基数格式位设置以十六进制输出的语句是( b )。 (a) cout< 开题报告 数学与应用数学 网络最大流问题算法研究 一、综述本课题国内外研究动态, 说明选题的依据和意义 最大流问题是指在一定的条件下, 要求流过网络的物流、能量流、信息流等流量为最大的问题[2]. 最大流问题已有50多年的研究历史, 这段时期内, 人们建立了最大流问题较 为完善的理论, 同时开发了大量优秀的算法. 如Ford 和Fulkerson 增截轨算法 [3]、Dinic 阻塞流算法、Goldberg 推进和重标号算法[6]以及Goldberg 和Rao 的二分长度阻塞流算法等等, 这些经典算法及相关技术对网络最大流问题的研究起到了非常重要的推动作用. 近年来, 随着计算机科学技术和网络的快速发展, 网络最大流问题得到了更深入的研究, 并极大地推动了最大流问题的研究进展. 然而, 研究工作仍未结束: 首先, 在理论算法研究方面, 人们还没有发现最大流问题算法时间复杂度的精确下界, 更没有任何一个通用算法达到或接近问题的下界; 其次, 在算法的实际性能方面, 目前算法的实际性能也不能满足许多应用问题的要求; 同时,最大流问题作为特殊的线性规划问题, 它远比一般线性规划问题容易解决, 发现应用领域中的问题和最大流问题的联系可以使应用问题更好地得到解决. 因此, 关于网络最大流问题的研究具有十分重要的理论意义和实用价值[5]. 最早的算法是Dantzig 提出的网络单纯刑法和Ford 和Fulkerson 的增载轨算法, 他们都是伪多项式时间算法, 分别由Dinic, Edmonds 和Karp 等提出. 1973年Dinic 首次获得了时间复杂度的核心因子为nm 算法. 以后的几十年中, 最大流算法获得了很大的进展. 在最大流问题中, ()nm O 时间界是一个自然的障碍. 如果我们把一个流沿从源到汇的各个路径进行分解, 根据流分解定理, 这些包含流的路径的总长度为()nm Θ.因此, 对每次利用一条曾接轨的算法, ()nm O 时间是这类算法的下界. 尽管这个下界对使用动态树数据结构或基于预流概念的算法是不适用的, 但在很长一段时间内, ()nm O 的 文献综述 数学与应用数学 网络最大流问题算法研究 最大流问题是指在一定的条件下,要求流过网络的物流、能量流、信息流等流量为最大的问题[2].最大流问题已有50多年的研究历史,这段时期内,人们建立了最大流问题较为完善的理论,同时开发了大量的算法.如Ford和Fulkerson增截轨算法、Dinic阻塞流算法、Goldberg推进和重标号算法[6]以及Goldberg和Rao的二分长度阻塞流算法等等,这些经典算法及相关技术对网络最大流问题的研究起到了非常重要的推动作用.近年来,随着计算机科学技术和网络的快速发展,网络最大流问题得到了更深入的研究,并极大地推动了最大流问题的研究进展.然而,研究工作仍未结束:首先,在理论算法研究方面,人们还没有发现最大流问题算法时间复杂度的精确下界,更没有任何一个通用算法达到或接近问题的下界; 其次,在算法的实际性能方面,目前算法的实际性能也不能满足许多应用问题的要求; 同时,最大流问题作为特殊的线性规划问题, 它远比一般线性规划问题容易解决,发现应用领域中的问题和最大流问题的联系可以使应用问题更好地得到解决.因此,关于网络最大流问题的研究具有十分重要的理论意义和实用价值[5]. 最早的算法是Dantzig[6]提出的网络单纯刑法和Ford和Fulkerson的增载轨算法, 他们都是伪多项式时间算法,分别由Dinic、Edmonds和Karp等提出.1973年Dinic首 次获得了时间复杂度的核心因子为nm算法.以后的几十年中,最大流算法获得了很 大的进展. 本文主要介绍的是网络最大流的几种主要算法,其中重点介绍了标号算法的详细 过程,其后给出了其在实际中的应用实例,后面介绍了现有的几种主要算法,虽然没 有给出具体的程序,但本文目的主要是了解最大流问题的解决思想,读者对网络流算 法有更深刻的认识,读者要想了解更多关于最大流问题的研究,详细可以参照Goldberg等人的研究成果, 这些程序在网上都可以轻松得到. 在这里就不再详细讲述. 下面简要介绍一下增载轨算法. 增载轨算法[5]: 沿剩余网络中从源到汇的有向路径推进流. 增载轨算法包括Ford 网络流基本概念 在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流，等等。50年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”，是网络应用的重要组成部分。在最近的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已不是什么稀罕的事了。本节着重介绍最大流(包括最小费用)算法，并通过实际例子，讨论如何在问题的原型上建立—个网络流模型，然后用最大流算法高效地解决问题。 1.问题描述如图5-1所示是联结某产品地v1和销售地v4的交通网，每一弧(vi,vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数表示这条运输线的最大通过能力。产品经过交通网从v1到v4。现在要求制定一个运输方案使从v1到v4的产品数量最多。 图5-1 图5-2 2.网络与网络流 给一个有向图N=(V，E)，在V中指定一点，称为源点(记为vs，和另一点，称为汇点(记为vt)，其余的点叫中间点，对于E中每条弧(vi，vj)都对应一个正整数c(vi，vj)≥O(或简写成cij)，称为f的容量，则赋权有向图N=(V，E，c，vs，vt)称为一个网络。如图5-1所给出的一个赋权有向图N就是一个网络，指定v1是源点，v4为汇点，弧旁的数字为cij。所谓网络上的流，是指 定义在弧集合E上一个函数f={f(vi，vj)}，并称f(vi，vj)为弧(vi，vj)上的流量(下面简记为fij)。如图5-2所示的网络N，弧上两个数，第一个数表示容量cij，第二个数表示流量fij。 3.可行流与最大流 在运输网络的实际问题中，我们可以看出，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0，源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。因此有： (1)容量约束：0≤f ij≤c ij，(v i,v j)∈E， (2)守恒条件 对于中间点：流入量=流出量；对于源点与汇点：源点的净流出量v s(f)=汇点的净流入量（-v t(f)） 的流f，称为网络N上的可行流，并将源点s的净流量称为流f的流值v(f)。 网络N中流值最大的流f*称为N的最大流。 4.可增广路径 所谓可增广路径，是指这条路径上的流可以修改，通过修改，使得整个网络的流值增大。 设f是一个可行流，P是从源点s到汇点t的一条路，若p满足下列条件： (1)在p上的所有前向弧(vi→vj)都是非饱和弧，即0≤f ij网络流算法
网络最大流问题概论
从一道题目的解法试谈网络流的构造与算法Word版
第10章-输入输出流
网络流模型总结
网络流算法讲座材料
网络流题目集锦
发学生第7次JAVA测试题第10章输入输出流内容20101211
浅谈网络流算法与几种模型转换
第10章 输入输出流
网络最大流问题算法研究【开题报告】
网络最大流问题算法研究【文献综述】
网络流详解(C++版)
相关主题
文本预览