Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


  1. 「COGS 741」负载平衡 - 费用流

    G 公司有 n 个沿铁路运输线环形排列的仓库,每个仓库存储的货物数量不等。如何用最少搬运量可以使 n 个仓库的库存数量相同。搬运货物时,只能在相邻的仓库之间搬运。

    于  COGS, Edmonds-Karp, 图论, 网络流, 网络流 24 题, 费用流 继续阅读

  2. 「COGS 740」分配问题 - 二分图最大权匹配

    n 件工作要分配给 n 个人做。第 i 个人做第 j 件工作产生的效益为 c[i][j]。试设计一个将 n 件工作分配给 n 个人做的分配方案,使产生的总效益最大。

    于  COGS, Edmonds-Karp, 二分图匹配, 图论, 网络流, 网络流 24 题, 费用流 继续阅读

  3. 「CTSC1999」星际转移 - 网络流

    现有 n 个太空站位于地球与月球之间,且有 m 艘太空船在其间来回穿梭。每个太空站可容纳无限多的人,第 i 个太空船只可容纳 H[i] 个人。每艘太空船将周期性地停靠一系列的太空站。每一艘太空船从一个太空站驶往任一太空站耗时均为 1。人们只能在太空船停靠太空站(或月球、地球)时上、下船。初始时所有人全在地球上,太空船全在初始站。求让所有人尽快地全部转移到月球上的最短时间。

    于  COGS, CTSC, Dinic, 图论, 枚举答案, 网络流, 网络流 24 题 继续阅读

  4. 「COGS 742」深海机器人 - 费用流

    有多个深海机器人到达深海海底后离开潜艇向预定目标移动。深海机器人在移动中还必须沿途采集海底生物标本。沿途生物标本由最先遇到它的深海机器人完成采集。每条预定路径上的生物标本的价值是已知的,而且生物标本只能被采集一次。深海机器人只能从其出发位置沿着向北或向东的方向移动,而且多个深海机器人可以在同一时间占据同一位置。

    于  COGS, Edmonds-Karp, 图论, 网络流, 网络流 24 题, 费用流 继续阅读

  5. 「COGS 739」运输问题 - 费用流

    W 公司有 m 个仓库和 n 个零售商店。第 i 个仓库有 ai a_i 个货物,第 j 个商店需要 bj b_j 个货物,从第 i 个仓库运输到第 j 个零售商店的费用为 cij c_{ij} ,要将所有货物运到商店,最小费用是多少?

    于  COGS, Edmonds-Karp, 图论, 网络流, 网络流 24 题, 费用流 继续阅读

  6. 「COGS 746」骑士共存 - 二分图最大独立集

    在一个 NN N * N 个方格的国际象棋棋盘上,马(骑士)可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍,骑士不得进入。问最多可以在棋盘上放多少个其实。

    于  COGS, Dinic, 图论, 最大独立集, 网络流, 网络流 24 题 继续阅读

  7. 「COGS 738」数字梯形 - 费用流

    一个数字梯形,共有 n 行,第一行有 m 个数字,每一行都比上一行多一个数字。从第一行的每一个数字开始,每一次向左下方或左上方走,直到最后一行,有以下三种规则:

    1. 任意两条路径没有公共部分;
    2. 任意两条路径只能在点(数字)上有公共部分,不能在边(数字与数字之间)上有公共部分;
    3. 任意两条路径可以在点上或边上有公共部分。

    求分别在这三种规则下的路径所经过数字总和的最大值。

    于  COGS, Edmonds-Karp, 图论, 网络流, 网络流 24 题, 费用流 继续阅读

  8. 「COGS 734」方格取数 - 二分图最大独立集

    在一个有 MN M * N 个方格的棋盘中,每个方格中有一个正整数。现要从方格中取数,使任意两个数所在方格没有公共边,且取出的数的总和最大。

    于  COGS, Dinic, 图论, 最大独立集, 网络流, 网络流 24 题 继续阅读

  9. 「COGS 439」软件补丁 - 记忆化搜索 + 位运算

    现在有一个软件,共有 n 个 BUG,开发人员开发了 m 个补丁,每个补丁有一个应用条件,要求某些 BUG 比如存在,某些 BUG 可以不存在,某些 BUG 存在或不存在都可以;每个补丁有一个影响,会使某些 BUG 消失,会使某些 BUG 产生;每个 BUG 有一个应用时间。问修复所有 BUG 需要的最短时间为多少。

    于  COGS, map, 位运算, 搜索, 网络流 24 题, 记忆化搜索 继续阅读

  10. 「COGS 727」太空飞行计划 - 最大权闭合图

    W 教授正在为国家航天中心计划一系列的太空飞行。可供选择的实验集合为 ,这些实验需要使用的全部仪器的集合为 。实验 Ej E_j 需要用到的仪器是 。仪器 Ik I_k 的费用为 ck c_k 。实验 Ej E_j 的赞助商为该实验结果支付 pj p_j 。设计方案使收益最大。

    于  COGS, Dinic, 图论, 最大权闭合图, 网络流, 网络流 24 题 继续阅读