有上下界网络流问地的题目

1、有上下界网络流问题1. 无源汇最大流2. 有源汇最大流3. 有源汇最小流1.无源汇最大流问题sgu194题意：给n个点，及m根pipe，每根pipe用来流躺液体的，单向的，每时每刻每根pipe流进来的物质要等于流出去的物质，要使得m条pipe组成一个循环体，里面流躺物质。并且满足每根pipe 一定的流量限制，范围为Li,Ri.即要满足每时刻流进来的不能超 过Ri（最大流问题），同时最小不能低于Li。例如：46（4 个点，6 个 pipe）12 1 3 （1->2 上界为3，下界为1）23 1 33 4 1 34 1 1 31 3 1 34 2 1 3可行流：再如：所有pipe的上界为2下

2、界为1的话，就不能得到一种可行流。题解：上界用ci表示，下界用bi表示。下界是必须流满的，那么对于每一条边，去掉下界后，其自由流为ci - bi。主要思想：每一个点流进来的流 二流出去的流对于每一个点i,令Mi= sum（i点所有流进来的下界流）-sum（i点所有流出去的下界流）如果Mi大于0，代表此点必须还要流出去 Mi的自由流，那么我们从源点连一条 Mi的边到该点。如果Mi小于0，代表此点必须还要流进来 Mi的自由流，那么我们从该点连一条 Mi的边到汇点。如果求S->T的最大流，看是否满流（S的相邻边都流满）。满流则有解，否则无解。zoj3229题意：经过构图之后得到这样的问题，源点

3、s,汇点t,有些边有上下界Li,Ri.求s->t 的最大流。题解: 满足所有下界的情况下，判断是否存在可行流，方法可以转化成上面无源汇上下界判断方法。只要连一条T- S的边，流量为无穷，没有下界，那么原图就得到一个无源汇的循 环流图。接下来的事情一样：原图中的边的流量设成自由流量ci - bi。新建源点SS汇点TT,求Mi，连边。然后求SS- TT最大流，判是否满流。判定有解之后然后求最大流，信息都在上面求得的残留网络里面。满足所有下界时，从s- t的流量为多少？后悔边s- t的边权！然后在残留网络中s- t可能还有些 自由流没有流满，再做一次s- t的最大流，所得到的最大流就是原问题的

4、最大流（内 含两部分：残留的自由流所得到的流 +后悔边s- t）。3.有源汇最小流 题意：经过构图之后得到这样的问题，源点s,汇点t,有些边有上下界Li,Ri.求s->t 的最小流。题解：同样先转换为无源汇网络流问题，添加t- s边权为无穷。那么最小流不就是在满足所有下界的情况的流么。即上面提到的，求得SS- TT的最大流之后，其后悔边s t的边权即为最小流。但是 wa 了，下面看一个 wa的例子：最后求得SS TT的最大流之后，得到后悔边 s t的边权为200，实际上该网络 最小流只要100 :s 1:1001 3:2003 2:2002 1:1002 t:100问题出在原图中存在环，

5、循环流，而我们没有利用，导致流增大了。解决方法：先不加tf s边权为无穷的边，求 SS- TT的最大流，如果还没有流满 则再加tf s边权为无穷的边，再求一次最大流得到后悔边 s- t就是原问题的最 小流了。zoj_3229_AC_code:/*求有源汇的最大流问题*/memset(i n,0,sizeof (in); /*初始化出度，入度，用于求Mi*/memset(out,0,sizeof (out);M= n+m+2; /* 初始化网络，设置源点汇点*/s= 0;t= M-1;cnt= -1;memset(mat,0,sizeof (mat);for(int i=1;i<=n;i+

6、) /*添加自由流 */for(int j=1;j<=Ci;j+) addEdge(i, n+Tij,Rij-Lij,0);inn+Tij+= Lij;outi+= Lij;for(i nt i=1;i< 二n ;i+) addEdge(s,i,Di,O);for(i nt i=1;i<=m;i+) addEdge (n+i,t,INF - Gi,O);in t+= Gi;out n+i+二 Gi;addEdge(t,s,INF,0); /* 添加一条 t s 的边，权值为 INF*/M+= 2; s = M-1; t = s-1; /* 添加 SS, TT*/ sum二0;

7、/*满流变量*/for(int i=0;i<M;i+) /* 根据 Mi 连边*/ if(ini > outi) addEdge(s,i,i ni - outi,0);sum+= in i - outi;else addEdge(i,t,outi - i n i,0);intmaxflow = dinic (); /*求 SS Tt 的最大流 */if(sum != maxflow) /*不满流则输出-1*/prin tf("-1nn");con ti nue;mats= 0; /* 删除 SS, TT*/matt= 0;M= n+m+2;s= 0;t= M-1

8、;maxflow= dinic (); /* 求s t的最大流，为原问题的解 */prin tf("%dn",maxflow);in tmm = -1;for(i nt i=1;i< 二n ;i+) for(int j=1;j<=Ci;j+) mm+;prin tf("%dn",Rij - edge2*mm.cap);prin tf("n");sgu_176_AC_code:/*有源汇的最小流*/Mi*/memset(i n,0,sizeof (in); /*初始化出度，入度，用于求memset(out,0,sizeof

9、(out);M= n+1; /*初始化网络，设置源点汇点*/s= 1;t= M-1;cnt= -1;memset(mat,0,sizeof (mat);for(int i=1;i<=m;i+) /* 添加自由流 */if(ci = 1) in vi += zi;outui += zi;addEdge (ui,vi,0,0);else addEdge (ui,vi,zi,0);M+= 2; s = M-1; t = s-1; /* 添加 SS, TT*/intsum = 0; /*满流变量 */for(int i=1;i<=n;i+) /* 根据 Mi 连边*/ if(ini >

10、; outi) addEdge(s,i,i ni - outi,0);sum+= in i - outi;else addEdge(i,t,outi - i n i,0);intmaxflow = dinic (); /*求SS TT的最大流，先流完途中的循环流 */intmmm = cnt; /* 记录新加的t f s无穷边的编号，以便求后悔边的权值*/addEdge(n,1,INF,0); /*添加一条 tf s 的边，权值为 INF*/maxflow+= dinic (); /*求 SSf TT 的最大流 */if(sum != maxflow) /* 不满流则输出-1*/prin tf("lmpossiblen");return。;printf("%dn",edgemmm+2.cap); /* in tmm = -1;boolfirst = 1;最小流为后悔边：sf t的权值*/for(i nt i=1;