AC. 梦想

线性规划与网络流目录下的文章

[BZOJ 3876] 支线剧情

题目描述 宅男JYY非常喜欢玩RPG游戏,比如仙剑,轩辕剑等等。不过JYY喜欢的并不是战斗场景,而是类似电视剧一般的充满恩怨情仇的剧情。这些游戏往往都有很多的支线剧情,现在JYY想花费最少的时间看完所有的支线剧情。 JYY现在所玩的RPG游戏中,一共有N个剧情点,由1到N编号,第i……
16/03/22 | 暂无评论 | 514阅读 阅读详情

有上下界网络流

有上下界网络流大致可以分为下面几类问题。 在下列叙述中,b(u,v)为边的流量下界,c(u,v)为边的流量上界,f(u,v)为边的实际流量,g(u,v)为边的自由流,即g(u,v) = f(u,v) - b(u,v)。 无源汇有上下界可行流 对于一个在无源汇有上下界网络的可行流,任意边应满足上下界限制b(u,v) ……
16/03/21 | 暂无评论 | 1,508阅读 阅读详情

[BZOJ 2502] 清理雪道

题目描述 滑雪场坐落在FJ省西北部的若干座山上。 从空中鸟瞰,滑雪场可以看作一个有向无环图,每条弧代表一个斜坡(即雪道),弧的方向代表斜坡下降的方向。 你的团队负责每周定时清理雪道。你们拥有一架直升飞机,每次飞行可以从总部带一个人降落到滑雪场的某个地点,然后再飞……
16/03/21 | 暂无评论 | 805阅读 阅读详情

[BZOJ 1834] 网络扩容

题目描述 给定一张有向图,每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求: 1、在不扩容的情况下,1到N的最大流; 2、将1到N的最大流增加K所需的最小扩容费用。 输入格式 输入文件的第一行包含三个整数N,M,K,表示有向图的点数、边数以及所需……
16/03/20 | 暂无评论 | 427阅读 阅读详情

[BZOJ 3931] 网络吞吐量

题目描述 路由是指通过计算机网络把信息从源地址传输到目的地址的活动,也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地,路由器需要选择最优的路径转发数据包。例如在常用的路由算法OSPF(开放式最短路径优先)中,路……
16/03/19 | 暂无评论 | 467阅读 阅读详情

[BZOJ 2424] 订货

题目描述 某公司估计市场在第i个月对某产品的需求量为Ui,已知在第i月该产品的订货单价为di,上个月月底未销完的单位产品要付存贮费用m,假定第一月月初的库存量为零,第n月月底的库存量也为零,问如何安排这n个月订购计划,才能使成本最低?每月月初订购,订购后产品立即到货,……
16/03/19 | 暂无评论 | 421阅读 阅读详情

[BZOJ 1822] 冷冻波

题目描述 WJJ喜欢“魔兽争霸”这个游戏。在游戏中,巫妖是一种强大的英雄,它的技能Frozen Nova每次可以杀死一个小精灵。我们认为,巫妖和小精灵都可以看成是平面上的点。 当巫妖和小精灵之间的直线距离不超过R,且巫妖看到小精灵的视线没有被树木阻挡(也就是说,巫妖和小精灵的……
16/03/19 | 暂无评论 | 572阅读 阅读详情

[BZOJ 1221] 软件开发

题目描述 某软件公司正在规划一项n天的软件开发计划,根据开发计划第i天需要ni个软件开发人员,为了提高软件开发人员的效率,公司给软件人员提供了很多的服务,其中一项服务就是要为每个开发人员每天提供一块消毒毛巾,这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒……
16/03/18 | 暂无评论 | 443阅读 阅读详情

[BZOJ 1061] 志愿者招募

题目描述 申奥成功后,布布经过不懈努力,终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题:为即将启动的奥运新项目招募一批短期志愿者。经过估算,这个项目需要N 天才能完成,其中第i 天至少需要Ai 个人。 布布通过了解得知,一共有M 类志愿者可以招募……
16/03/06 | 2 条评论 | 1,912阅读 阅读详情

[ZJOI 2013] 防守战线

题目描述 战线可以看作一个长度为n 的序列,现在需要在这个序列上建塔来防守敌兵,在序列第i 号位置上建一座塔有Ci 的花费,且一个位置可以建任意多的塔,费用累加计算。有m 个区间[L1, R1], [L2, R2], …, [Lm, Rm],在第i 个区间的范围内要建至少Di 座塔。求最少花费。 输入格……
16/03/05 | 4 条评论 | 1,317阅读 阅读详情