有上下界网络流问题

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

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

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

4、源汇最小流题意：经过构图之后得到这样的问题，源点s，汇点t，有些边有上下界Li,Ri.求s->t的最小流。题解：同样先转换为无源汇网络流问题，添加t-s边权为无穷。那么最小流不就是在满足所有下界的情况的流么。即上面提到的，求得SS-TT的最大流之后，其后悔边st的边权即为最小流。但是wa了，下面看一个wa的例子：最后求得SS-TT的最大流之后，得到后悔边s-t的边权为200,实际上该网络最小流只要100：s-1:1001-3:2003f2:2002f1:1002ft:100问题出在原图中存在环，循环流，而我们没有利用，导致流增大了。解决方法：先不加t-s边权为无穷的边，求SS-TT的最大

5、流，如果还没有流满则再加t-s边权为无穷的边，再求一次最大流得到后悔边s-t就是原问题的最小流了。zoj_3229_AC_code:/*求有源汇的最大流问题*/memset(in,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(inti=1;i<=n;i+)/*添加自由流*/for(intj=1;j<=Ci;j+)addEdge(i,n+Tij,Rij-Lij,0);inn+Tij

6、+=Lij;outi+=Lij;for(inti=1;i<=n;i+)addEdge(s,i,Di,0);for(inti=1;i<=m;i+)addEdge(n+i,t,INF-Gi,0);int+=Gi;outn+i+=Gi;addEdge(t,s,INF,0);/*添加一条ts的边，权值为INF*/M+=2;s=M-1;t=s-1;/*添加SS，TT*/sum=0;/*满流变量*/for(inti=0;i<M;i+)/*根据Mi连边*/if(ini>outi)addEdge(s,i,ini-outi,0);sum+=ini-outi;elseaddEdge(i,t

7、,outi-ini,0);intmaxflow=dinic();/*求SSTt的最大流*/if(sum!=maxflow)/*不满流则输出-1*/printf("-1nn");continue;mats=0;/*删除SS，TT*/matt=0;M=n+m+2;s=0;t=M-1;maxflow二dinic();/*求st的最大流，为原问题的解*/printf("%dn",maxflow);intmm=-1;for(inti=1;i<=n;i+)for(intj=1;j<=Ci;j+)mm+;printf("%dn",Rij

8、-edge2*mm.cap);printf("n");sgu_176_AC_code:/*有源汇的最小流*/memset(in,0,sizeof(in);/*初始化出度，入度，用于求Mi*/memset(out,0,sizeof(out);M=n+1;/*初始化网络，设置源点汇点*/s=1;t=M-1;cnt=-1;memset(mat,0,sizeof(mat);for(inti=1;i<=m;i+)/*添加自由流*/if(ci=1)invi+=zi;outui+=zi;addEdge(ui,vi,0,0);elseaddEdge(ui,vi,zi,0);M+=2;

9、s=M-1;t=s-1;/*添加SS，TT*/intsum=0;/*满流变量*/for(inti=1;i<=n;i+)/*根据Mi连边*/if(ini>outi)addEdge(s,i,ini-outi,0);sum+=ini-outi;elseaddEdge(i,t,outi-ini,0);intmaxflow=dinic();/*求SSTT的最大流，先流完途中的循环流*/intmmm=cnt;/*记录新加的ts无穷边的编号，以便求后悔边的权值*/addEdge(n,1,INF,0);/*添加一条ts的边，权值为INF*/maxflow+=dinic();/*求SSTT的最大流*

10、/if(sum!=maxflow)/*不满流则输出-1*/printf("Impossiblen");return0;printf("%dn",edgemmm+2.cap);/*最小流为后悔边：st的权值*/intmm=-1;boolfirst=1;for(inti=1;i<=m;i+)if(first)first=0;elseprintf("");if(ci)printf("%d",zi);elseprintf("%d",zi-edge2*i-2.cap);printf("n");仅供个人用于学习、研究；不得用于商业用途Forpersonaluseonlyinstudyandresearch;notforcommercialuse.Nurfurdenpers?nlichenfurStudien,Forschung,zukommerziellenZweckenverwendetwerden.Pourl'etudeetlarechercheun