网络流建模汇总

所需积分/C币:50 2012-03-02 20:10:28 504KB PDF
2
收藏 收藏
举报

网络流建模的汇总 ·最大流 ·最小割 ·最小费用最大流 ·有上下界流
《剪刀石头布》 .25 《小结》 26 最大流 《POJ1149PIGS》 【题目大意】 有M个猪圈,每个猪圈里初始时有若T头猪。一开始所有猪圈都是关闭的。依 次来了N个顾客,每个顾客分别会打开指定的儿个猪圈,从中买若干头猪。每 个顾客分别都有他能够买的数量的上限。每个顾客走后,他打开的那些猪圈中的 猪,都可以被任意地调换到其它开着的猪圈里,然后所有猪圈重新关上。问总共 最多能卖出多少头猪。(1<=N<=100,1<=M<=1000) 举个例子来说。有3个猪圈,初始时分别有3、1和10头猪。依次来了3个顾客, 第一个打开1号和2号猪圈,最多买2头;第二个打开1号和3号猪圈,最多买 3头;第三个打开2号猪圈,最多买6头。那么,最好的可能性之一就是第一个 顾客从1号圈买2头,然后把1号圈剩下的1头放到2号圈;第二个顾客从3 号圈买3头;第三个顾客从2号圈买2头。总共卖出2+3+2=7头。 【建模方法】 不难想象,这个问题的网络模型可以很直观地构造出来。就拿上面的例了来说, 可以构造出图1所示的模型(图中凡是没有标数字的边,容量都是∞): 三个顾客,就有三轮交易,每一轮分别都有3个猪圈和1个顾客的结点。 ·从源点到第一轮的各个猪圈各有一条边,容量就是各个猪圈里的猪的初始 数量。 从各个顾客到汇点各有一条边,容量就是各个顾客能买的数量上限 在某一轮中,从该顾客打开的所有猪圈都有一条边连向该顾客,容量都是 最后一轮除外,从每一轮的ⅰ号猪圈都有一条边连向下一轮的ⅰ号猪圈, 容量都是∞,表示这一轮剩下的猪可以留到下一轮。 ·最后一轮除外,从每一·轮被打开的所冇猪圈,到下·轮的同样这些猪圈, 两两之间都要连一条边,表示它们之间可以任意流通 sink 1 3 1 1 source 2 2 2 10 图1 这个网络模型的最大流量就是最多能卖岀的数量。图中最多有 2+N+MXN≈100,000个结点。这个模型虽然很直观,但是结点数太多∫,计算速 度肯定会很慢。其实不用再想别的算法,就让我们继续上面的例子,用合并的方 法来简化这个网络模型。 首先,最后一轮中没有打开的猪圈就可以从图中删掉了,也就是图2中红色 的部分,显然它们对整个网络的流量没有任何影叫。 5 sink 1 1 source 2 2 2 10 3 3 13 图2 接着,看图2中蓝色的部分。根据我总结出的以下几个规律,可以把这4个 点合并成一个: 规律1.如果几个结点的流量的来源完全相同,则可以把它们合并成一个 规律2.如果几个结点的流量的去向完全相同,则可以把它们合并成一个。 规律3.如果从点u到点v有一条容量为∞的边,并且点v除了点u以外没 有别的流量来源,则可以把这两个结点合并成一个。 根据规律1,可以把蓝色部分右边的1、2号结点合并成一个;根据规律2 可以把蓝色部分左边的1、2号结点合并成一个;最后,根据规律3,可以把蓝 色部分的左边和右边(已经分别合并成了一个结点)合并成一个结点。于是,图 2被简化成了图3的样子。也就是说,最后一轮除外,每一轮被打开的猪圈和下 轮的同样这些猪圈都可以被合并成一个点 6 sink source 1 2 10 3 图3 接着,根据规律3,图3中的蓝色结点、2号猪圈和1号顾客这三点可以合 并成一个;图3中的两个3号猪圈和2号顾客也可以合并成一个点。当然,如果 两点之问有多条同向的边,则这些边可以合并成一条,容量相加,这个道理很简 单,就不用我多说了。最终,上例中的网络模型被简化成了图4的样了。 sink 3 2 3 Source 10 图4 让我们从图4中重新总结一下构造这个网络模型的规则: 每个顾客分别用一个结点来表示 对于每个猪圈的第一个顾客,从源点向他迕一条边,容量就是该猪圈里的 猪的初始数量。如果从源点到一名顾客有多条边,则可以把它们合并成 条,容量相加 对于每个猪圈,假设有n个顾客打开过它,则对所有整数i∈[1,n),从该 猪圈的第ⅰ个顾客向第i+1个顾客连一条边,容量为∞ 从各个顾客到汇点各有一条边,容量是各个顾客能买的数量上限 拿我们前面直在讲的例了来说:1号猪圈的第个顾客是1号顾客,所以 从源点到1号顾客有一条容量为3的边;1号猪圈的第二个顾客是2号顾客,因 此从1号顾客到2号顾客有一条容量为∞的边;2号猪圈的第一个顾客也是1号 顾客,所以从源点到1号顾客有一条容量为1的边,和之前己有的一条边合并起 来,容量变成4;2号猪圈的第二个顾客是3号顾客,因此从1号顾客到3号顾 客有一条容量为∞的边;3号猪圈的第·个顾客是2号顾客,所以从源点到2号 顾客有一条容量为10的边。 新的网络模型中最多只有2+N=102个结点,计算速度就可以相当快了。可 以这样理解这个新的网络模型:对于某一个顾客,如果他打开了猪圈h,则在他 走后,他打开的所有猪圈里剩下的猪都有可能被换到h中,因而这些猪都有可能 被h的下一个顾客买走。所以对于一个顾客打开的所有猪圈,从该顾客到各猪圈 的下一个顾客,都要连一条容量为∞的边。 在面对网络流问题时,如果一时想不出很好的构图方法,不如先构造一个最 直观,或者说最“硬来”的模型,然后再用合并结点和边的方法来简化这个模 型。经过简化以后,好的构图思略自然就会涌现出来了。这是解决网络流问题 的一个好方法。 《POJ1637 Sightseeing tour》 【题目大意】 混合图欧拉回路。(1<=N<=200,1<M<=1000) 【建模方法】 把该图的无向边随便定向,计算每个点的入度和出度。如果有某个点出入度 之差为奇数,那么背定不存在欧拉回路。因为欢拉回路要求每点入度=出度, 也就是总度数为偶数,存在奇数度点必不能有欧拉回路。 好了,现在每个点入度和出度之差均为偶数。那么将这个偶数除以2,得ⅹ 也就是说,对于每一个点,只要将x条边改变方向(入>出就是变入,出>入就是 变出),就能保证出=入。如果每个点都是出=入,那么很明显,该图就存在欧拉 回路。 现在的问题就变成了:我该改变哪些边,可以让每个点出=入?构造网络流 模型。首先,有向边是不能改变方向的,要之无用,删。一开始不是把无向边定 向了吗?定的是什么向,就把网络构建成什么样,边长容量上限1。另新建s和 t。对于入>出的点u,连接边u,t)、容量为x,对于出>入的点v,连接边(s,y), 容量为ⅹ(注意对不同的点ⅹ不同)。之后,察看是否有满流的分配。有就是能 冇欧拉回路,没冇就是没冇。欧拉回路是哪个?察看流值分配,将所有流量非0 (上限是1,流值不是0就是1)的边反向,就能得到每点入度=出度的欧拉图。 由于是满流,所以每个入>出的点,都有ⅹ条边进来,将这些进来的边反向 oK,入=出了。对于出>入的点亦然。那么,没和s、t连接的点怎么办?和s连 接的条件是出>入,和t连接的条件是入>出,那么这个既没和s也没和t连接的 点,自然早在开始就已经满足入=出了。那么在网络流过程中,这些点属于“中 间点”。我们知道中间点流量不允许有累积的,这样,进去多少就出来多少,反 向之后,自然仍保持平衡。 所以,就这样,混合图欧拉回路问题,解了 《POJ23910 mbrophobic bovines》 【题目人意】 给定一个无向图,点i处有Ai头牛,点ⅰ处的牛棚能容纳Bi头牛,求一个最短时 间T使得在T时间内所有的牛都能进到某一牛棚里去。(1<=N<=200,1<=M<= 1500,0<=Ai<=10000<=Bi<=1000,1<=Dj<=1,0000000 【建模方法】 将每个点i拆成两个点,连边(s,Ai),(r",t,Bi)。二分最短时间T,若d[iUjl<=T (o[]]表小点ij之间的最短距离)则加边(’门”,∞)。每次根据最大流调整二分 的上下界即可。 种错误的建图方法,即不拆点,见下图: 420 0 5 其中每条无向边表示两条方向相反的有向边,容量均为∞ 二分到T=70的时候,显然我们只加入∫(2,3)和(3,4)两条无向边,因为只有 这两对点间的最短距离小于等于70。但是从图中也可以看出,由于没有拆点, 点2也可以通过这两条边到达点4,而实际上这是不允许的。也就是说我们所加 的限制条件没有起到作用。由此可见,只有拆点才是正确的做法 《POJ2699 The Maximum Number of Strong Kings》 【题目大意】 一场联赛叮以表小成一个完全图,点表小参赛选手,任意两点uV之间有且仅有 一条有向边(u,v)或(u),表示u打败v或ν打败u。一个选手的得分等于被他打 败的选手总数。一个选手被称为“ strong king”当且仅当他打败了所有比他分高 的选手。分数最高的选手也是 strong king。现在给出某场联赛所有选手的得分序 列,由低到高,问合理安排每场比赛的结果后最多能有几个 strong king。已知选 手总数不超过10个 【建模方法】 此题乍看之下无从下手,但是注意到 strong king只能在分数最高的若干人当中 生,而总人数只有10个,故我们可以枚举 strong king的个数C,那么分数最高 的C个便是 strong king,接下来按下列方法构图:每场比赛i作为一个点(总共 tot=n*(n-1)个,加边(s,,1);每名选于j作为一个点,加边(j,t, score[]),并再 拉出一个点〕,如果j是 strong king,则加边(, J,score[i]-Maxj)(注意此处 corell Max]有可能为负,所以要在构图之前判一下。设当前分数最小的 strong king 为m,若 score[mj]<Maxm则直接停止枚举,因为m每场都赢也不够把所有 比他分高的选手赢个遍),其中Max[表示比选手i分数高的选手总数:否则加边 (,j, score[j])。对每场比赛i,设参赛的两名选手为U,Ⅵ且 score[ui]<= score[M] 若U是 strong king且 scorel]< score[v,则城(,U,1):否则加边(,U’,1),(V', 1)。当某次最大流小于tot时停止枚举即可 对每名选手j,所有连到j的边G,j表示比赛i必须让j贏。若j是 strong king,则 , j, scored-Max])的目的是除去必须让j羸的那Max场以外,剩下的 sorell Max场可以随意赢剩下的N-MaX名选于。对于非 strong king的选于也是类似 的作用。 这里提一下我的一种错误建模方法: 每名选于i用三个点的门,表示,加边(s, I score[i]),(",t,N-1- score[j]),而则 允当那个被拉出来的点。其他细节不再提。这样构图之后每一·条s-流表示场 比赛,看似合理但其实是错误的,因为它没有考虑到任何两名选于之间以能进行 一场比赛,而这个网络中可能存在两条st流,它们关联的是同样的两名选手, 只不过胜负对调。故以后在构图时要时刻关注它的严谨性和正确性

...展开详情
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
上传资源赚积分or赚钱
    最新推荐