www.cc465.com
当前位置: 六合财经论坛 > www.cc465.com > 正文

传说中的收集流24题

时间:2019-05-11   浏览次数:

  成立源点s到每个点的边,流量为点的货色量,费用为0;成立各个点到汇点t的边,流量为所有货色的平均数,费用为0;成立每个点和上一点和下一点的边,流量为inf,费用为1;求出最小费用最大流,OK!

  数字点进行拆点连边,若是点或者边只能够走一次就把流量设为1,费用为点权相反数,当然边的权为0。成立源点和汇点,求最小费用最大流,输出相反数,OK!

  通过的建图,拆点间的边暗示本来的边,有用节点不克不及反复走,所有拆点间的边权为1。由于取源点或汇点的连边权为1,所以每一个点都只能做为边的起点或竣事点一次。如许每找到一个婚配,两头的点就能够串正在一个径上,能够削减一条径。所以点数-最大婚配=ans

  建模:从西到东再到西,现实上就是从西向东飞两次。最东和最西的城市拆点后流量为2,其他城市拆点后流量为1,费用为-1;正在毗连曲航的边,流量为1,费用为0,跑最小费用最大流,OK!可是,若是只要工具两个城市,也就是流量为1,那么要进行特判。

  这是收集流吗?分明就是一个形态压缩最短。别离记实有一种形态到另一种形态所需要的前提和发生的变化。求从全数缝隙到没有缝隙的最短经(时间)。

  建模:成立源点s和汇点t,成立s点到代表队的边,权为代表人数;成立餐桌到汇点的边,权为餐桌的人数;成立代表队到每一个餐桌的边,权为1;跑最大流。

  建模:把正副驾驶员别离做为二分图,以正在能够同机飞翔的飞翔员间建边,流量为1。成立源点s和正飞翔员间的边,流量1。成立副飞翔员和汇点t的有向边,流量1。dinic,最大流。

  按照钥匙的形态分层,也就是暗示当前形态的变量有坐标(x,y)还要加上当前具有的钥匙z。当然钥匙形态z需要形态压缩。然后sp求最短,此中达到方针的最短就是谜底。

  建模方式取第15题不异,全数正在于由的点断可能呈现竖曲的环境,也就是两头点不异,如许跑最大流会有负环。因而正在离散时要把摆布端点做一下处置,也就是乘以2,若是两头点不相等,左端点减1,相等则左端点减1。

  最小不订交径笼盖:把每个点进行拆点,把2点之间连不边,;原有边照旧建边,留意入点和出点,权为1;成立源点和汇点,并别离毗连他们取入点和出点的边,权为1。然后就是二分图婚配了。所有点数(不含源点和汇点)减去最大婚配就是谜底。

  收集流24题,传说中进修的收集流的必做标题问题。今天终究做完了,感受涉及的模子并不多,有一些我传闻过的就没有涉及。但仍是总结如下:

  第二步:求最长上升子序列的条数。由于每个数只能用一次,所以每个点拆点,并毗连边权为1的边。毗连可能(f[]相连而且数值添加)的毗连边,权为1。毗连s取所有f[i]==1的点,毗连t取所有f[i]==最长上升子序列长度 的点,边权1。跑最大流,就是谜底。

  源点s到各个仓库点建边,流量为货色量,费用为0;各个商铺点到汇点t,流量为需要的货色量,费用为0;各个仓库和各个商铺连边,流量inf,费用为对应两点件运输的费用,跑最小费用最大流,OK!

  建模:按照时间进行分层。顺次列举时间,时间每添加以,则添加(太空坐+2)个点(一层),毗连上一次取这一次的点,边为飞船可从上一时辰的某坐到这一时辰的某坐,边权为飞船的容量。s代表地球,t代表月球。跑最大流,若是人数大于等于需要运送的人数,则输出时间,不然时间加1,添加一层,继续跑最大流。

  成立源点s,并毗连s到人的边,流量为1,费用为0;成立汇点t,并毗连工做到t的边,流量为1,费用为0;毗连每小我到每一项工做的边,流量为1,费用为对应的效益,跑最小费用最大流,获得最小收益。若是把费用取反,求最大费用最大流,获得最大收益。

  留意点:当油量变为0时,从动成立油坐并充满油;到油坐从动加油;还有一个坑,当达到起点刚好油量为0时,不再加油。

  该题取题17根基不异,正在坐标(x,y)的根本上添加当前点残剩的油量z,如许F(x,y,z)暗示正在(x,y)点,正在残剩油量为z的环境下的最小破费。跑sp。

  现实上仍是上一个题,只是改为扣问能够放几多个球。采用每次个数加1的方式加边,然后跑最大流。如许若是球数-dinic()柱子数,证明放不下了,谜底就是球数-1。

  建模:典型的费用流。初做该题,环节正在于把每天想象成两个点,需要的清洁餐巾(B)和用过餐巾的处置(A);还有s,t的理解,可认为用过的通过s,t做为办理坐进行分发处置。如许每天需要的清洁毛巾由三个来历,新购入s,慢洗A(i-n),快洗A(i-m);每天用过的餐巾有三个处置渠道,慢细B(i+n),快洗B(i+m),留待明天处置A(i+1)。正在加上每天需要餐巾和用过餐巾都是cost(i),能够理解为清洁的餐巾由源点s代购,用过的餐巾由汇点t收集,再由s点转给各个用过餐巾点。

  建模:成立源点s和汇点t,让s取所有试验相毗连,边权为试验赞帮的钱数;让所有仪器取t相毗连,边权为仪器费用;让所有试验取对应的仪器链接,边权为inf,跑最大流就能够了。较着要么是赞帮费大于仪器费,那么获得的是仪器费(赞帮费-仪器费=收益);要么是仪器费大于赞帮费,那么获得的是赞帮费(不值得做,仍是赞帮费-赞帮费=收益=0)。如许所有的赞帮费减去获得的成果就是收益。

  第一步:最长上升子序列长度,能够用DP获得。同时的到f[i]:暗示到第i个数并以之结尾的最长上升子序列长度。

  建模:对所有区间的摆布端点进行离散化,毗连前一点到后一段的边,流量inf,费用0;成立源点s到1号点的边,流量为k,费用为0;成立随后一个点到汇点t的边,流量为k,费用为0;成立每个区间的摆布端点的边,流量为1,费用为区间长度。跑最大费用最大流。相当于跑了k次最短,并把对应的废掉。

  建模:费用流,没什么好说的。有一点其时比力懵,若何只要第一次获得费用,现实方式很简单:建2条边,一条流量1,费用是指定值,一条流量inf,费用为0。

  建模:成立源点s和汇点t,让s和t别离于二分图的一侧相连,边权为方格内的数。毗连相邻的方格边权为inf,求最大流(最小割)。成果就是所以格内数的和减去最小割。较着选了两头的方格就不选周边相邻的方格,所以就割边正在对应的边上。

  建模:成立源点s和汇点t,毗连s点取每品种型点的边,权为所选类型的数量;毗连各个类型点取对应类型的标题问题的边,权为1,每个类型只选择给标题问题一次;毗连每个标题问题和汇点t的边,权为1,每个标题问题只选1次。跑最大流。

  相关链接:



Copyright 2018-2020 http://www.52yxpk.com All Rights Reserved.版权所有 @