最小割模型的应用.ppt

网络流 最小割模型的应用,一引例二基本概念三三个重要问题四经典例题欣赏,2023年4月22日星期六,2,一引例：运输方案UVA1069,如图为连接产品产地V1和销地V6的交通网，每一条边（Vi，Vj）表示从Vi到Vj的运输线，产品经这条边由Vi输送到Vj，边上的数字表示这条运输线的最大通行能力（简称容量）。产品经过交通网从V1输送到V6，现要求制定一个输送方案，使得从V1运到V6的产品数量最多。,2023年4月22日星期六,3,如图为一个可行的输送方案，边上的数字表示该运输线的实际运输量（单位：吨）。该运输方案表示：2吨产品沿有向路P1（V1，V2，V4，V6）运到销地；1吨产品沿有向路P2（V1，V2，V5，V6）运到销地；2吨产品沿有向路P3（V1，V3，V5，V6）运到销地。总共有5吨产品从V1运到V6。,2023年4月22日星期六,4,一引例：运输方案UVA1069,算法分析与设计 可行的运输方案必须满足以下三个条件：（1）实际运输量不能是负的；（2）每条边的实际运输量不能大于该边的容量；（3）除了起点V1和终点V6，对其他顶点（中间点）来说，不能囤积物资，即运到它那儿的物资是多少，从它那儿运走的物资也应该是多少。思考：如何改进运输方案？即根据这个运输网，是否可增大运输量？,2023年4月22日星期六,5,一引例：运输方案UVA1069,我们找到一条有向路P4（V1，V2，V3，V4，V6）可再增加1吨物资运输量，改进的方案如图所示：,2023年4月22日星期六,6,一引例：运输方案UVA1069,观察有向路P6（V1，V3，V2，V4，V6）中，将正方向的边（V1，V3）、（V2，V4）、（V4，V6）都可增加运输量，而反方向的边（V3，V2）的运输量为1，现将反向边（V3，V2）的运量调到正向边（V2，V4）上去完成，这样有向路P6（V1，V3，V2，V4，V6）的运量可增加1。,2023年4月22日星期六,7,一引例：运输方案UVA1069,至此，再找不到可“改进”的有向路了，所以，该交通网的最大运输量为8吨。,2023年4月22日星期六,8,一引例：运输方案UVA1069,本题小结 通过上述实例分析，包含了流量因素的问题，是一类特殊的图。引例给出的交通网其具体的物理模型是多种多样的。例如网络的有向边可以表示为城市之间的公路、电信网之间的通讯线路、天然气站之间的输气管道等；边的容量则可以表示为允许通过的物资数量、汽车数量、速率或最大信号流量等。这一类特殊的图，称为网络流图。网络流图中需要解决的基本问题有最大流问题、最大流最小割问题、最小费用最大流问题等。,2023年4月22日星期六,9,一引例：运输方案UVA1069,二基本概念：什么是流网络,流网络G=(V,E)是一个有向图，其中每条边（弧）(u,v)E均有一个非负容量c(u,v)=0。如果(u,v)不属于E，则假定c(u,v)=0。流网络中有两个特别的顶点：源点s和汇点t。一个流网络的实例（红色数字表示边的最大容量，蓝色数字表示边上的实际流量）：,2023年4月22日星期六,10,二基本概念：什么是流,对一个流网络G=(V,E)，每条边(u,v)上给定一个实数f(u,v)，满足：0=f(u,v)=c(u,v)，则f(u,v)称为边(u,v)上的流量。其中满足f(u,v)=c(u,v)的边称为饱和边。如果有一组流量满足条件：源点s：流出量=整个网络的流量 汇点t：流入量=整个网络的流量 中间点：总流入量=总流出量 那么整个网络中的流量成为一个可行流。整个流网络G的流量为：|f|=f(s,v)(vV)或|f|=f(u,t)(uV)即从源出发的所有流的总和或到达汇的所有流的总和,2023年4月22日星期六,11,二基本概念：什么是流,三个重要性质 容量约束：对所有的u,vV，要求f(u,v)=c(u,v)；平衡约束（反对称性）：对所有的u,vV，要求f(u,v)=-f(v,u)；流守恒性：对所有uV-s,t，要求f(u,v)=0(vV)。（流量平衡方程）,2023年4月22日星期六,12,二基本概念：什么是最大流,对于一个流网络G=(V,E)，在其可行流中，流量最大的一个流即最大流。最大流可能不止一个。如右图中可行流7也是最大流。,2023年4月22日星期六,13,一个可行流：5,一个可行流：7,二基本概念：什么是残留网络,在给定的流网络G=(V,E)中，设f为G中的一个流，并考察一对定点u,vV，在不超过容量c(u,v)的条件下，从u到v之间可以压入的额外网络流量，即(u,v)的残留容量，记为Gf=(V,Ef)。定义cf(u,v)为残留网络Gf中边(u,v)的容量。如果弧(u,v)E或弧(v,u)E，则(u,v)Ef，且cf(u,v)=c(u,v)-f(u,v)。而由所有属于G的边的残留容量所构成的带权有向图就是G的残留网络。,2023年4月22日星期六,14,二基本概念：什么是增广路径,增广路径为在残留网络Gf中从s到t的一条简单路径。若边(u,v)的方向与该路径的方向一致，称(u,v)为正向边（正向弧），正向边的全体记为P+；若边(u,v)的方向与该路径的方向相反，称为逆向边（反向弧），逆向边的全体记为P-。增广路径上所有的边满足：对所有正向边有：f(u,v)0，即P-中的每一条边都是非零流边。将增广路径中最大量为p的残留网络定义为：cf(p)=mincf(u,v)|(u,v)在增广路径上,2023年4月22日星期六,15,二基本概念：什么是增广路径,2023年4月22日星期六,16,简单路径：13245中，(1,3)(2,4)(4,5)是正向边，(3,2)是逆向边。,二基本概念：什么是增广路径,2023年4月22日星期六,17,已形成1235和1245两条路径余下两条增广路径：135 13245增加流量=？2+2=4,1,2,3,4,5,4,3,2,6,2,5,2,4,2,2,2,2,s,t,二基本概念：什么是割,2023年4月22日星期六,18,割（CUT）是流网络中顶点的一个划分，它把流网络G(V,E)中的所有顶点划分成两个顶点集合S和T（T=V-S），其中源点sS，汇点tT，记为CUT(S,T)。如果一条边（弧）的两个顶点分别属于顶点集S和T（即一个顶点在S中，另一个顶点在T中），那么这条边称为割CUT(S,T)的一条割边。从S指向T的割边是正向割边；从T指向S的割边是逆向割边。割CUT(S,T)中所有正向割边的容量之和称为割CUT(S,T)的容量。不同割的容量不同。,二基本概念：什么是割,2023年4月22日星期六,19,顶点集合S=1，2，3和T=4，5构成一个割。割的容量为：3+4=7。,1,2,3,4,5,4,3,2,6,2,5,4,4,3,1,1,3,s,t,源点：s=1；汇点：t=5。框外是容量，框内是流量。,二基本概念：什么是割,2023年4月22日星期六,20,1,2,3,4,5,4,3,2,6,2,5,4,4,3,1,1,3,s,t,顶点集合S=1，3和T=2，4，5构成一个割。正向割边：12；35逆向割边：23,割的容量：4+4=8割的正向流量：4+2=6逆向割的流量：1,二基本概念：什么是割,2023年4月22日星期六,21,1,2,3,4,5,4,3,2,6,2,5,4,4,3,1,1,3,s,t,顶点集合S=1，3，5和T=2，4能否构成一个割？,二基本概念：什么是割,2023年4月22日星期六,22,顶点集合S=1，3，4和T=2，5能否构成一个割？同构变形,三三个重要问题：最大流问题,最大流定理 根据可行流f为最大流，当且仅当不存在关于f的增广路径。证明：若f是最大流，但图中存在关于f的增广路径，则可以沿该增广路径增广，得到的是一个更大的流，与f 是最大流矛盾。所以，最大流不存在增广路径。增广路定理 当且仅当由当前的流f压得的残留网络中不存在增广路径时，流f的流量|f|达到最大。,2023年4月22日星期六,23,三三个重要问题：最大流问题,Ford-Fulkerson方法 根据增广路定理，我们可以设计出最基本的求最大流的方法Ford-Fulkerson方法。开始将流网络G=(V,E)中的流f置为零流，即对于(u,v)E时，f(u,v)=0。然后构建残留网络，寻找增广路径增广，再修改残留网络，重复此过程，直到无法找到增广路径。具体步骤如下：（1）如果存在增广路径，就找出一条增广路径；（2）然后沿该条增广路径进行更新流量（增加流量）。,2023年4月22日星期六,24,三三个重要问题：最大流问题,2023年4月22日星期六,25,开始流量为：sum=0,一条增广路径:1235d=min4,2,4=2增加流量：2sum=2,s,t,s,t,三三个重要问题：最大流问题,2023年4月22日星期六,26,一条增广路径:1245d=min4-2,3,5=2增加流量：2sum=2+2=4,1,2,3,4,5,4,3,2,6,2,5,2,4,2,s,t,1,2,3,4,5,4,3,2,6,2,5,2,4,2,s,t,2,2,2,三三个重要问题：最大流问题,2023年4月22日星期六,27,1,2,3,4,5,4,3,2,6,2,5,2,4,2-1=1,s,t,2,2,2,1,2,3,4,5,4,3,2,6,2,5,2,4,2,s,t,2,2,2,1,1,1,一条增广路径:13245d=min6,2,3-2,5-2=1增加流量：1sum=4+1=5,23减少1，加到2423减的1由13补充1,三三个重要问题：最大流问题,2023年4月22日星期六,28,1,2,3,4,5,4,3,2,6,2,5,2,4,2-1=1,s,t,2,2,2,1,1,1,一条增广路径:135d=min6-1,4-2=2增加流量：2sum=5+2=7,1,2,3,4,5,4,3,2,6,2,5,2,4,2-1=1,s,t,2,2,2,1,1,1,2,2,三三个重要问题：最大流问题,基于DFS的Ford-Fulkerson方法找一条增广路径：1、先设d为为正无穷（d为可增加流）若（u,v）是正向边：d=min(d,c(u,v)-f(u,v)若（u,v）是逆向边：d=min(d,f(u,v)2、对与该增广路径上的边 若（u,v）是正向边，f(u,v)=f(u,v)+d；若（u,v）是逆向边，f(u,v)=f(u,v)-d；增广后，总流量增加了d。,2023年4月22日星期六,29,三三个重要问题：最大流问题,Ford-Fulkerson方法的伪代码：Ford-Fulkerson(G,s,t)1 for each edge(u,v)EG/初始化 2 do fu,v0 3 fv,u0 4 while there exists a path p from s to t in the residual network Gf 5 do cf(p)mincf(u,v)|(u,v)is in p 6 for each edge(u,v)in p 7 do fu,vfu,v+cf(p)8 fv,ufv,u-cf(p),2023年4月22日星期六,30,三三个重要问题：最大流问题,Ford-Fulkerson方法核心：第48行的while循环反复找出Gf中的增广路径p，并把沿p的流f加上其残留容量cf(p)。当不再有增广路径时，流f就是一个最大流。设n=|V|，m=|E|，U表示增广次数，则理论时间复杂度：O(nmU)。参考程序片段见flow_FF.pas。,2023年4月22日星期六,31,三三个重要问题：最大流问题,基于BFS的Edmonds-Karp（EK）算法找一条增广路径：EK算法是基于Ford-Fulkerson方法，唯一的区别是从第4行开始用BFS（宽搜）来实现对增广路径p的计算。对于EK算法，每次用一遍BFS寻找从源点s到汇点t的最短路作为增广路径，然后增广流量f并修改残量网络，直到不存在新的增广路径。EK算法的理论时间复杂度为：O(nm2)，由于BFS要搜索全部小于最短距离的分支路径之后才能找到终点，因此频繁的BFS效率是比较低的。类似用BFS实现的还有Dinic算法。参考程序片段见flow_EK.pas和flow_Dinic.pas。,2023年4月22日星期六,32,三三个重要问题：最大流问题,基于SAP算法（最短增广路算法）找一条增广路径：（1）定义距离标号为到汇点距离的下界。（2）在初始距离标号的基础上，不断沿可行弧找增广路增广，一般采用DFS深度优先。可行弧定义为：(i,j)|hi=hj+1（3）遍历当前节点完成后，为了使下次再来的时候有路可走，重标号当前节点为：minhj|(i,j)+1（注意要满足距离标号的性质：不超过真实距离）,2023年4月22日星期六,33,三三个重要问题：最大流问题,（4）重标号后当前节点处理完毕。当源点被重标号后，检查其距离标号，当大于顶点数时，图中已不存在可增广路，此时算法结束；否则再次从源点遍历。（5）理论时间复杂度为：O(n2m)。,2023年4月22日星期六,34,三三个重要问题：最大流问题,2023年4月22日星期六,35,开始流量为：sum=0所有结点的标号为：0,对1号结点进行重标号形成一条路径:12,s,t,s,t,0,0,0,0,0,1,0,0,0,0,三三个重要问题：最大流问题,2023年4月22日星期六,36,2号结点无法向外流通，对2号结点进行重标号，12的路径无法再形成通路，13形成通路,3号结点无法向外流通，对3号结点进行重标号，13的路径无法再形成通路,s,t,s,t,1,1,0,0,0,1,1,0,1,0,三三个重要问题：最大流问题,2023年4月22日星期六,37,再次回到1号结点进行重标号,一条增广路径:135,s,t,s,t,2,1,0,1,0,2,1,0,1,0,三三个重要问题：最大流问题,初始标号初始化时全部设为0。理论上可以写出许多子程序并迭代实现，但判断琐碎，没有层次，实践中用递归简单明了，增加的常数复杂度比起SAP速度微乎其微却极大降低编程复杂度，易于编写调试。,2023年4月22日星期六,38,三三个重要问题：最大流问题,GAP优化 注意到在某次增广后，最大流可能已经求出，因此算法做了许多无用功。可以发现，距离标号是单调增的。这就启示我们如果标号中存在“间隙”，则图中不会再有可增广路，于是算法提前终止。实践中可以使用数组counti记录标号为i的顶点个数，若重标号使得count中原标号项变为0，则停止算法。,2023年4月22日星期六,39,三三个重要问题：最大流问题,2023年4月22日星期六,40,SAP算法的伪代码：SAP-ALGORITHM(G,s,t)1 initialize flow f to 0 2 do BFS to calculate d of each vertex/In fact,we can initialize d to 0.3 i s 4 while d(s)n/n is the amount of vertexes in G 5 if there exists j that(i,j)Ef and d(i)=d(j)+1 6 then do add vertex i into augmenting path p 7 i j 8 if i=t/come to t,三三个重要问题：最大流问题,2023年4月22日星期六,41,8 if i=t 9 then do augment flow f along p 10 i s/go back s to find another way 11 else if there exists j that(i,j)Ef 12 then d(i)mind(j)+1|(i,j)Ef 13 else d(i)n/or 14 if is then do delete i in augmenting path p 15 i last vertex in p 16 return f,三三个重要问题：最小割问题,2023年4月22日星期六,42,流与割的关系 网络流量：5 割的流量：,三三个重要问题：最小割问题,2023年4月22日星期六,43,定理一 如果f是网络中的一个流，CUT(S,T)是任意一个割，那么f的值等于正向割边的流量与负向割边的流量之差。证明：设X和Y是网络中的两个顶点集合，用f(X,Y)表示从X中的一个顶点指向Y的一个顶点的所有弧（弧尾在X中，弧头在Y中：XY）的流量和。只需证明：f=f(S,T)-f(T,S)即可。,三三个重要问题：最小割问题,2023年4月22日星期六,44,推论一 如果f是流网络中的一个流，CUT(S,T)是流网络中一个割，那么f的值不超过割CUT(S,T)的容量。推论二 流网络中的最大流不超过任何割的容量。,三三个重要问题：最小割问题,2023年4月22日星期六,45,定理二 在任何网络中，如果f是一个流，CUT(S,T)是一个割，且f的值等于割CUT(S,T)的容量，那么f是一个最大流，CUT(S,T)是一个最小割（容量最小的割）。,三三个重要问题：最小割问题,2023年4月22日星期六,46,定理三：最大流最小割定理（Ford-Fulkerson定理）在任何的网络中，最大流的值等于最小割的容量。证明一：简单证明 假设f是流网络G=(V,E)的一个最大流。先证明f是G的割：f是G的最大流，根据最大流定理，Gf的残留网络中不存在ST的增广路径=S,T分属两个连通分量=f是G的割。再证f是G的最小割：利用反证法，假设|f1|Gf1残留网络中存在ST的增广路径=S,T不属于两个连通分量=与前提条件不符，故f是G的最小割。,三三个重要问题：最小割问题,2023年4月22日星期六,47,证明二：数学证明（Ford-Fulkerson，1962）存在一个割，其容量=最大流的流量。亦即，具有容量限制的最大流的流量=最小割的容量。由于具有最大流量的流存在，所以我们可以取一个最大流f。递归的定义一个顶点集S，如下：source在S中；其次，若x在S中，且f(xy)0，则y也在S中。反复使用上述过程，最后可以得到一个由顶点构成的集合，即S。由于图中只有有限多个顶点，所以上述过程也一定会在有限多个步骤之后终止。,三三个重要问题：最小割问题,2023年4月22日星期六,48,还需证明sink不在S中，如下，假如sink在S中，则有一列顶点，x_1=source，x_2，x_n=sink，使得：r_i=maxc(x_i，x_i+1)-f(x_i，x_i+1)，f(x_i+1，x_i)0,三三个重要问题：最小割问题,2023年4月22日星期六,49,对于该序列中的任意两个相邻顶点x，y，其中x=x_i在y=x_i+1前面，都有C(xy)-f(xy)0或者f(yx)0，取两者当中较大的一个，这个数就是r_i。然后取所有r_i中最小的一个，有限多个正数的最小值还是一个正数（严格大于0），记这个正数为r。由此对f作一些修改可以构造一个新的流，若边xy在上述序列中，则将流量f(xy)修改为f(xy)+r，否则就不作改变。这样得到的函数确实是一个流，满足容量限制，而且其流量比f的流量要大r0。这就和f是最大流矛盾。这就证明了sink不在S中，从而证明了S确实为一个割。,三三个重要问题：最小割问题,2023年4月22日星期六,50,下面证明割S的容量=流f的流量。首先有等式，f的流量=f(S,V-S)-f(V-S,S)。由S的构造，容易看出第一项f(S,V-S)=C(S,V-S)=割S的容量。第二项f(V-S,S)=0。证毕。说明：记号V-S表示不在S中的顶点全体，亦即表示集合S在V中的余集。,三三个重要问题：最大权闭合图问题,2023年4月22日星期六,51,在一个有向图的流网络G=(V,E)中，选取一些点构成集合，记为V，且集合中的出边（即集合中的点的向外连出的弧），所指向的终点（弧头）也在V中，则称V为闭合图。在所有闭合图中，集合中点的权值之和最大的V，我们称V为最大权闭合图。,左图中闭合图有：5、2,5、4,52,4,5、3,4,51,2,3,4,5、1,2,4,5最大权闭合图为：3,4,5,三三个重要问题：最大权闭合图问题,2023年4月22日星期六,52,如何求最大权闭合图？首先我们将其转化为一个流网络。构造一个源点s，汇点t。我们将s与所有权值为正的点连一条容量为其权值的边，将所有权值为负的点与t连一条容量为其权值的绝对值的边，原来的边将其容量定为正无穷。（如何证明？）,三三个重要问题：最大权闭合图问题,2023年4月22日星期六,53,定理一 最小割为简单割。证明：定义：简单割即割集的每条边都与s或t关联。那么为什么最小割是简单割呢？因为除s和t之外的点间的边的容量是正无穷，最小割的容量不可能为正无穷。所以，得证。,三三个重要问题：最大权闭合图问题,2023年4月22日星期六,54,定理二 流网络中的简单割与原图中闭合图存在一一对应的关系。（即所有闭合图都是简单割，简单割也必定是一个闭合图）。证明：证明闭合图是简单割（反证法）：如果闭合图不是简单割。那么说明有一条边是容量为正无穷的边，则说明闭合图中有一条出边的终点不在闭合图中，矛盾。证明简单割是闭合图：因为简单割不含正无穷的边，所以不含有连向另一个集合（除t）的点，所以其出边的终点都在简单割中，满足闭合图定义。得证。,三三个重要问题：最大权闭合图问题,2023年4月22日星期六,55,定理三 最小割所产生的两个集合中，其源点s所在集合（除去s）为最大权闭合图。证明：记一个简单割的容量为C，且源点s所在集合为N，汇点t所在集合为M。则C=M中所有权值为正的点的权值（即s与M中点相连的边的容量）+N中所有权值为负的点权值的绝对值（即N中点与t点相连边的容量），记为：C=x1+y1。记N这个闭合图的权值和为W。则W=N中权值为正的点的权值-N中权值为负的点的权值的绝对值，记为：W=x2-y2。,三三个重要问题：最大权闭合图问题,2023年4月22日星期六,56,则：W+C=x1+y1+x2-y2。很明显，y1=y2，所以W+C=x1+x2。因为x1为M中所有权值为正的点的权值，x2为N中权值为正的点的权值。所以x1+x2=所有权值为正的点的权值之和，记为Q。即W+C=Q，得到：W=Q-C。此时可得闭合图的权值与简单割的容量的关系，如下：因为Q为定值，所以要使得W最大，须C为最小，即此时的简单割为最小割，闭合图为其源点s所在集合（除去s）。得证。,三三个重要问题：最大权闭合图问题,2023年4月22日星期六,57,结论：将最大权闭合图问题转化为了求最小割的问题。根据最大流最小割定理，即可将问题转化为求最大流的问题。,幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。我们的问题就是，每位小朋友应该怎样投票，才能使冲突数最小？,2023年4月22日星期六,58,四经典例题：善意投票SHTSC2007,输入输出格式 第一行中有两个整数n，m（2=n=300，1=m=n*(n-1)/2)，分别表示总人数和好朋友的对数。第二行中有n个整数，其中：第i个整数表示第i个小朋友的意愿，当它为1时表示同意睡觉，当它为0时表示反对睡觉。接下来的m行，每行有两个整数i，j，表示i，j是一对好朋友，我们保证任何两对i，j不会重复。输出一个整数，即可能的最小冲突数。,2023年4月22日星期六,59,四经典例题：善意投票SHTSC2007,题目概述 n个小朋友要投票决定是否睡午觉。一开始他们都有自己的决定，但由于存在若干朋友关系，若一个小朋友的选择和朋友不同那么冲突数会增加，而我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。,2023年4月22日星期六,60,四经典例题：善意投票SHTSC2007,1,3,2,s,t,2023年4月22日星期六,61,四经典例题：善意投票SHTSC2007,1,2,s,t,3,4,5,6,算法分析与设计 设计这样一个网络：使得源点连向每一个持有第一种态度的同学，每一个持有第二种态度的同学连向汇点。任意有朋友关系的小朋友都连一条边。我们规定一个同学和源点相连表示其持有第一种态度，和汇点相连表示其持有第二种态度，那么不难发现一种合法的方案必然对应网络的一种割，因为没有一个人可以保持两种态度。,2023年4月22日星期六,62,四经典例题：善意投票SHTSC2007,由于每个人最终态度和初始态度相反会增加1单位的冲突值，每对朋友冲突也会增加1单位的冲突值，因此我们使得原来的网络的每个流量都为1。如果割除源点连出的边或者连到汇点的边就可以表示为这个小朋友最终态度和初始态度相反，而对于割除朋友之间的边就可以表示为朋友之间的态度发生冲突。由于使得冲突数最小，自然也就是要求得一个最小割。,2023年4月22日星期六,63,四经典例题：善意投票SHTSC2007,样例分析,2023年4月22日星期六,64,四经典例题：善意投票SHTSC2007,1,3,2,1,1,1,s,1,t,1,1,每对朋友之间都连双向的边，所有边的流量均为1。,样例分析,2023年4月22日星期六,65,四经典例题：善意投票SHTSC2007,1,2,s,1,t,1,1,3,4,5,6,1,1,1,1,1,四经典例题：最大获利NOI2006,THU集团旗下的CS&T通讯公司在新一代通讯技术血战的前夜，需要做太多的准备工作，仅就站址选择一项，就需要完成前期市场研究、站址勘测、最优化等项目。在前期市场调查和站址勘测之后，公司得到了一共N个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需要投入的成本也是不一样的，所幸在前期调查之后这些都是已知数据：建立第i个通讯中转站需要的成本为Pi（1=i=N）。另外公司调查得出了所有期望中的用户群，一共M个。关于第i个用户群的信息概括为Ai，Bi和Ci：这些用户会使用中转站Ai和中转站Bi进行通讯，公司可以获益Ci。（1=i=M，1=Ai,Bi=N）THU集团的CS&T公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利=获益之和-投入成本之和）,2023年4月22日星期六,66,题目概述 选择建立一些适当的通讯站（点）为一些用户群提供通讯支持（边）点：需要付出成本 边：可以获得收益（关联两点已经选择）净获利=边收益-点成本 最大,2023年4月22日星期六,67,四经典例题：最大获利NOI2006,算法分析与设计 满足最大权闭合图模型：有向图，点有权（权可正可负）要求选择一个点集S 若有边ba，则若bS，必须有aS 要求S中所有点的权和最大 在本题中：若需要支持某个用户群，必须建立相应的中转站：“用户群中转站”中转站权为负，表示需要付出成本 用户群权为正，表示收益,2023年4月22日星期六,68,四经典例题：最大获利NOI2006,2023年4月22日星期六,69,样例分析,3,4,3,2,3,S,用户群,中转站,-1,-2,-3,-4,-5,四经典例题：最大获利NOI2006,s,+,3,4,3,2,根据最大权闭合图模型，添加源、汇，构造流网络：,用户群,中转站,t,3,1,2,3,4,5,2023年4月22日星期六,70,四经典例题：最大获利NOI2006,s,+,3,4,3,2,考虑网络中的一个割S，S，对于弧ab由于容量无穷大不允许 a属于S 而b不属于S即不允许 只选择a，不选择b,用户群,中转站,t,3,1,2,3,4,5,2023年4月22日星期六,71,S,四经典例题：最大获利NOI2006,s,+,3,4,3,2,若某用户群a不属于S，则割的容量加上 profit(a)若某中转站b属于S，则割的容量加上 cost(b),用户群,中转站,t,3,1,2,3,4,5,2023年4月22日星期六,72,S,四经典例题：最大获利NOI2006,净收益=选择用户群收益-选择中转站成本 所有用户群收益-未选择用户群-选择中转站成本 所有用户群收益-(未选择用户群+选择中转站成本)所有用户群收益-S，S割的容量所有用户群收益 一定 净收益最大 等价于 割容量最小 问题转化为求网络的最小割最大流,2023年4月22日星期六,73,四经典例题：最大获利NOI2006,算法实现：简单的最大流方法（Ford-Fulkerson）：80分 最短增广路算法（SAP）：100分,2023年4月22日星期六,74,四经典例题：最大获利NOI2006,四经典例题：植物战僵尸NOI2009,植物大战僵尸是最近十分风靡的一款小游戏。其中植物防守，而僵尸进攻。现在，我们将要考虑的问题是游戏中僵尸对植物的进攻，请注意，本题中规则与实际游戏有所不同。游戏中有两种角色植物和僵尸，每个植物有一个攻击位置集合，它可以对这些位置进行保护；而僵尸进攻植物的方式是走到植物所在的位置上并将其吃掉。游戏的地图可以抽象为一个N行M列的矩阵，行从上到下用0到N-1编号，列从左到右用0到M-1编号；在地图的每个位置上都放有一个Plant，为简单起见，我们把位于第r行第c列的植物记为Pr,c。植物分很多种，有攻击类、防守类和经济类等等。为了简单的描述每个Plant，定义Score和Attack如下：,2023年4月22日星期六,75,四经典例题：植物战僵尸NOI2009,僵尸的进攻必须从地图的右侧开始，且只能沿着水平方向向左进行移动。僵尸攻击植物的唯一方式就是走到该植物所在的位置并将植物吃掉。也就是说，对于第r行的进攻，僵尸必须首先攻击Pr,M-1；若需要对Pr,c（0=cM-1）攻击，必须将Pr,M-1，Pr,M-2，Pr,c+1先击溃，并移动到位置（r,c）才可进行攻击。在本题中，植物的攻击力是无穷大的，一旦僵尸进入某个植物的攻击位置，该僵尸会被瞬间消灭，而该僵尸没有时间进行任何攻击操作。因此，即便僵尸进入了一个植物所在的位置，但该位置属于其他植物的攻击位置集合，则僵尸会被瞬间消灭而所在位置的植物则安然无恙（在我们的设定中，植物的攻击位置不包含自身所在位置，否则你就不可能击溃它了）。僵尸的目标是对植物的阵地发起进攻并获得最大的能源收入。每一次，你可以选择一个可进攻的植物进行攻击。本题的目标为，制定一套僵尸的进攻方案，选择进攻哪些植物以及进攻的顺序，从而获得最大的能源收入。,2023年4月22日星期六,76,四经典例题：植物战僵尸NOI2009,题目概述 有一些植物，每个植物携带有一定的资源（可正可负），且有一个攻击范围，可以保护攻击位置上的另一个植物。有一群僵尸从右向左进攻植物，僵尸不能走到植物的攻击范围内。任务是求一个进攻方案，使得僵尸获得的资源尽可能多。图中箭头指向为保护关系。例如：(2,2)被(1,1)保护。(3,1)(3,2)都不可以吃。,2023年4月22日星期六,77,算法分析与设计 把每个植物当做一个顶点。把植物携带的资源数目作为顶点的权值。以植物之间的保护关系建立边（即每个植物指向保护它自己的植物）。对于互相保护的植物，即形成环的点，它们的权值是无法取到的，应把它们先去掉。不难发现，选出去攻击的植物，它们指向的点（也就是保护它的植物）必定也在我们的攻击序列里。这些点实质上就是一个闭合子图，而现在又要求植物的价值和最大，此时最大权闭合子图的模型就非常明显了。,2023年4月22日星期六,78,四经典例题：植物战僵尸NOI2009,满足最大权闭合图模型：有向图，点有权（权可正可负）要求选择一个点集S 若有边ba，则若bS，必须有aS 要求S中所有点的权和最大 在本题中：源点连向所有正权的点，流量为正权值大小 所有的负权点连向汇点，流量为负权值的绝对值 原来的保护关系ba建立边ba，流量为无穷 正权总和-最小割即为最大的价值,2023年4月22日星期六,79,四经典例题：植物战僵尸NOI2009,2023年4月22日星期六,80,样例分析,1,2,3,4,10,5,6,20,-10,-5,100,100,四经典例题：植物战僵尸NOI2009,2023年4月22日星期六,81,5，6互相依赖，不可能被攻击到。我们可以用拓扑排序去除图中的环依赖结构，以简化图。,1,2,3,4,10,5,6,20,-10,-5,100,100,四经典例题：植物战僵尸NOI2009,2023年4月22日星期六,82,将图转置，发现一个合法的攻击方案是一个闭合子图，由于我们的目标就是最大化攻击方案的点权值和，就是要求一个最大闭合子图，只需转化为网络流模型即可解决。,1,2,3,4,10,20,-10,-5,四经典例题：植物战僵尸NOI2009,2023年4月22日星期六,83,建立最大权闭合图，如图所示：Maxflow=5 最大权闭合图的权值为：(10+20-5)=25。,四经典例题：植物战僵尸NOI2009,四经典例题：上学路线AHOI2006,可可和卡卡家住在合肥市的东郊，每天上学他们都要转车多次才能到达市区西端的学校。有一天他们发现每天上学的乘车路线不一定是最优的。合肥市共有N个公交车站，将它们编号为1.N，可可和卡卡家住在1号汽车站附近，学校在N号汽车站。市内有M条直达汽车路线，执行第i条路线的公交车往返于站点pi和qi之间，从起点到终点需要花费的时间为ti（1=i=M，1=pi,qi=N）。两个人坐在电脑前，根据上面的信息很快就算出了最优的乘车方案。然而可可忽然有了一个鬼点子，他想趁卡卡不备，在卡卡的输入数据中删去一些路线，从而让卡卡的程序得出的答案大于实际的最短时间。而对于每一条路线i事实上都有一个代价ci：删去路线的ci越大卡卡就容易发现这个玩笑，可可想知道什么样的删除方案可以达到他的目的而让被删除的公交车路线ci之和最小。,2023年4月22日星期六,84,题目概述 在给定的一个图中，删除每一条边都有一个代价，要求使用最小的代价删除若干条边，使得删完后的图的最短路比原来的要大。,2023年4月22日星期六,85,四经典例题：上学路线AHOI2006,算法分析与设计 首先使用一个简单的Dijkstra算法求出起点到每个点的最短距离d(i)。在最短路算法执行完毕后，即可得到源点（1号结点）到其它结点i的最短路长度d(i)。构造一个新的网络G=V,E，其中对于任意一条边ei=(pi,qi,ti,ci)E，若d(qi)=d(pi)+ti，将其保留在E中，令之容量为ci。不难发现，在原图G中任何一个从1到N的最短路都是新网络G中的一条1到N的通路。这时问题即为删除最小代价的边使得起点和终点不联通。很明显的最小割的模型。,2023年4月22日星期六,86,四经典例题：上学路线AHOI2006,样例分析 如图，其中括号里的数字为删除边的代价。,2023年4月22日星期六,87,1,2,3,4,6,5,15,11,14,12,11,13,11,四经典例题：上学路线AHOI2006,样例分析 由图可知，最短路走法为1-2-6，1-5-6，长度为2。那么我们建立的一个新的网络就是下面的那样，此时从源点到汇点的每一条路径都对应原图中的最短路。我们必须删除一些边使得源与汇不连通，又由于每条边的流量都是我们去除掉这个边的代价，因而整个网络的最小割便是我们的最小代价。因为最小割为5（1-2,5-6切除），所以原图对应的最小代价便是5。,2023年4月22日星期六,88,四经典例题：上学路线AHOI2006,本题小结 在这类基于最小割定义的直接应用中，最小割模型的建立往往比较简单，但常常又和一些新颖的知识融合在一起。这样一来便不能直接地套用模型，而是需要使用一些知识与技巧，逐步将问题化归到最小割模型，使其成为某些主算