线性规划与网络流目录下的文章
[BZOJ 3876] 支线剧情
题目描述
宅男JYY非常喜欢玩RPG游戏,比如仙剑,轩辕剑等等。不过JYY喜欢的并不是战斗场景,而是类似电视剧一般的充满恩怨情仇的剧情。这些游戏往往都有很多的支线剧情,现在JYY想花费最少的时间看完所有的支线剧情。
JYY现在所玩的RPG游戏中,一共有N个剧情点,由1到N编号,第i……
有上下界网络流
有上下界网络流大致可以分为下面几类问题。
在下列叙述中,b(u,v)为边的流量下界,c(u,v)为边的流量上界,f(u,v)为边的实际流量,g(u,v)为边的自由流,即g(u,v) = f(u,v) - b(u,v)。
无源汇有上下界可行流
对于一个在无源汇有上下界网络的可行流,任意边应满足上下界限制b(u,v) ……
[BZOJ 2502] 清理雪道
题目描述
滑雪场坐落在FJ省西北部的若干座山上。
从空中鸟瞰,滑雪场可以看作一个有向无环图,每条弧代表一个斜坡(即雪道),弧的方向代表斜坡下降的方向。
你的团队负责每周定时清理雪道。你们拥有一架直升飞机,每次飞行可以从总部带一个人降落到滑雪场的某个地点,然后再飞……
[BZOJ 1834] 网络扩容
题目描述
给定一张有向图,每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求: 1、在不扩容的情况下,1到N的最大流; 2、将1到N的最大流增加K所需的最小扩容费用。
输入格式
输入文件的第一行包含三个整数N,M,K,表示有向图的点数、边数以及所需……
[BZOJ 3931] 网络吞吐量
题目描述
路由是指通过计算机网络把信息从源地址传输到目的地址的活动,也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地,路由器需要选择最优的路径转发数据包。例如在常用的路由算法OSPF(开放式最短路径优先)中,路……
[BZOJ 2424] 订货
题目描述
某公司估计市场在第i个月对某产品的需求量为Ui,已知在第i月该产品的订货单价为di,上个月月底未销完的单位产品要付存贮费用m,假定第一月月初的库存量为零,第n月月底的库存量也为零,问如何安排这n个月订购计划,才能使成本最低?每月月初订购,订购后产品立即到货,……
[BZOJ 1822] 冷冻波
题目描述
WJJ喜欢“魔兽争霸”这个游戏。在游戏中,巫妖是一种强大的英雄,它的技能Frozen Nova每次可以杀死一个小精灵。我们认为,巫妖和小精灵都可以看成是平面上的点。 当巫妖和小精灵之间的直线距离不超过R,且巫妖看到小精灵的视线没有被树木阻挡(也就是说,巫妖和小精灵的……
[BZOJ 1221] 软件开发
题目描述
某软件公司正在规划一项n天的软件开发计划,根据开发计划第i天需要ni个软件开发人员,为了提高软件开发人员的效率,公司给软件人员提供了很多的服务,其中一项服务就是要为每个开发人员每天提供一块消毒毛巾,这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒……
[BZOJ 1061] 志愿者招募
题目描述
申奥成功后,布布经过不懈努力,终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题:为即将启动的奥运新项目招募一批短期志愿者。经过估算,这个项目需要N 天才能完成,其中第i 天至少需要Ai 个人。 布布通过了解得知,一共有M 类志愿者可以招募……
[ZJOI 2013] 防守战线
题目描述
战线可以看作一个长度为n 的序列,现在需要在这个序列上建塔来防守敌兵,在序列第i 号位置上建一座塔有Ci 的花费,且一个位置可以建任意多的塔,费用累加计算。有m 个区间[L1, R1], [L2, R2], …, [Lm, Rm],在第i 个区间的范围内要建至少Di 座塔。求最少花费。
输入格……
12