大赛要求车手们从一颗与这 颗行星之间没有任何航路的天体出发,访问这 颗行星每颗恰好一次。超能电驴有两种移动模式:高速航行模式和能力爆发模式。在高速航行模式下,超能电驴会沿星际航路高速航行。在能力爆发模式下,经过一段时间的定位之后,它能瞬间移动到任意一个行星。在使用高速航行模式的时候,只能由每个星球飞往引力比它大的星球,否则赛车就会发生爆炸。求完成比赛的最少时间。
「SDOI2015」星际战争 - 网络流
Y 军团一共派遣了 个巨型机器人进攻 X 军团的阵地,其中第 个巨型机器人的装甲值为 。当一个巨型机器人的装甲值减少到 0 或者以下时,这个巨型机器人就被摧毁了。X 军团有 个激光武器,其中第 个激光武器每秒可以削减一个巨型机器人 的装甲值。激光武器的攻击是连续的。这种激光武器非常奇怪,一个激光武器只能攻击一些特定的敌人。Y 军团需要知道 X 军团最少需要用多长时间才能将 Y 军团的所有巨型机器人摧毁。
「COGS 741」负载平衡 - 费用流
G 公司有 n
个沿铁路运输线环形排列的仓库,每个仓库存储的货物数量不等。如何用最少搬运量可以使 n
个仓库的库存数量相同。搬运货物时,只能在相邻的仓库之间搬运。
「COGS 740」分配问题 - 二分图最大权匹配
有 n
件工作要分配给 n
个人做。第 i
个人做第 j
件工作产生的效益为 c[i][j]
。试设计一个将 n
件工作分配给 n
个人做的分配方案,使产生的总效益最大。
「CTSC1999」星际转移 - 网络流
现有 n
个太空站位于地球与月球之间,且有 m
艘太空船在其间来回穿梭。每个太空站可容纳无限多的人,第 i
个太空船只可容纳 H[i]
个人。每艘太空船将周期性地停靠一系列的太空站。每一艘太空船从一个太空站驶往任一太空站耗时均为 1。人们只能在太空船停靠太空站(或月球、地球)时上、下船。初始时所有人全在地球上,太空船全在初始站。求让所有人尽快地全部转移到月球上的最短时间。
「COGS 742」深海机器人 - 费用流
有多个深海机器人到达深海海底后离开潜艇向预定目标移动。深海机器人在移动中还必须沿途采集海底生物标本。沿途生物标本由最先遇到它的深海机器人完成采集。每条预定路径上的生物标本的价值是已知的,而且生物标本只能被采集一次。深海机器人只能从其出发位置沿着向北或向东的方向移动,而且多个深海机器人可以在同一时间占据同一位置。
「COGS 739」运输问题 - 费用流
W 公司有 m
个仓库和 n
个零售商店。第 i
个仓库有 个货物,第 j
个商店需要 个货物,从第 i
个仓库运输到第 j
个零售商店的费用为 ,要将所有货物运到商店,最小费用是多少?
「JSOI2008」最大数 - Splay
现在请求你维护一个数列,要求提供以下两种操作:
- 查询操作。
语法:
Q L
功能:查询当前数列中末尾L
个数中的最大的数,并输出这个数的值。 限制:L
不超过当前数列的长度。 - 插入操作。语法:
A n
功能:将n
加上t
,其中t
是最近一次查询操作的答案(如果还未执行过查询操作,则t = 0
),并将所得结果对一个固定的常数D
取模,将所得答案插入到数列的末尾。 限制:n
是非负整数并且在长整范围内。
注意:初始时数列是空的,没有一个数。
Edmonds-Karp 费用流学习笔记
有一类网络流问题,最大流并不唯一,而每一条边都有一个单位流量的费用,最优解的目标是保证流量最大的前提下使总费用最小。单纯的最大流可以使用 Edmonds-Karp 算法求解,但这个算法不够优,最常用的是 Dinic 算法。但 Edmonds-Karp 确是最小费用流问题最常用的算法。
「NOIP2010」关押罪犯 - 二分图染色
S 城现有两座监狱,一共关押着 N
名罪犯,编号分别为 1 ~ N
,我们用“怨气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名罪犯之间的积怨越多。每年每一对有仇恨的罪犯会发生一次冲突。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力。那么,应如何分配罪犯,才能使 Z 市长看到的那个冲突事件的影响力最小,求这个最小值是多少?