Menci

眉眼如初,岁月如故

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


  1. 「NOIP2013」华容道 - BFS + SPFA

    1. 在一个 n×m n \times m 棋盘上有 n×m n\times m 个格子,其中有且只有一个格子是空白的,其余 n×m1 n \times m - 1 个格子上每个格子上有一个棋子,每个棋子的大小都是 1×1 1 \times 1 的;
    2. 有些棋子是固定的,有些棋子则是可以移动的;
    3. 任何与空白的格子相邻(有公共的边)的格子上的棋子都可以移动到空白格子上。游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。

    给定一个棋盘,游戏可以玩 q q 次,当然,每次棋盘上固定的格子是不会变的,但是棋盘上空白的格子的初始位置、指定的可移动的棋子的初始位置和目标位置却可能不同。第 i i 次玩的时候,空白的格子在第 EXi EX_i 行第 EYi EY_i 列,指定的可移动棋子的初始位置为第 SXi SX_i 行第 SYi SY_i 列,目标位置为第 TXi TX_i 行第 TYi TY_i 列。

    假设小 B 每秒钟能进行一次移动棋子的操作,而其他操作的时间都可以忽略不计。请你告诉小 B 每一次游戏所需要的最少时间,或者告诉他不可能完成游戏。

    于  BFS, CodeVS, NOIP, SPFA, 搜索, 最短路 继续阅读

  2. 「ZJOI2006」物流运输 - 最短路 + DP

    物流公司要把一批货物从码头 A A 运到码头 B B 。由于货物量比较大,需要 n n 天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线,以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在,有的时候某个码头会无法装卸货物。这时候就必须修改运输路线,让货物能够按时到达目的地。但是修改路线是一件十分麻烦的事情,会带来额外的成本。因此物流公司希望能够订一个 n n 天的运输计划,使得总成本尽可能地小。

    于  BZOJ, COGS, DP, ZJOI, 最短路 继续阅读

  3. 「JSOI2016」飞机调度 - 最短路 + 网络流

    JSOI 王国里有 N N 个机场,编号为 1 1 N N 。从 i i 号机场到 j j 号机场需要飞行 Ti,j T_{i, j} 的时间。由于风向,地理位置和航空管制的因素,Ti,j T_{i, j} Tj,i T_{j, i} 并不一定相同。

    此外,由于飞机降落之后需要例行维修和加油。当一架飞机降落 k k 号机场时,需要花费 Pk P_k 的维护时间才能再次起飞。

    JS Airways 一共运营 M M 条航线,其中第 i i 条直飞航线需要在 Di D_i 时刻从 Xi X_i 机场起飞,不经停,飞往 Yi Y_i 机场。

    为了简化问题,我们假设 JS Airway 可以在 0 0 时刻在任意机场布置任意多架加油维护完毕的飞机;为了减少飞机的使用数,我们允许 JS Airways 增开任意多条临时航线以满足飞机的调度需求。

    JYY 想知道,理论上 JS Airways 最少需要多少架飞机才能完成所有这 M M 个航班。

    于  Dinic, Floyd, JSOI, 最短路, 网络流 继续阅读

  4. 「BZOJ 2143」飞飞侠 - 最短路

    飞国是一个 NM N * M 的矩形方阵,每个格子代表一个街区。飞国是没有交通工具的。飞侠完全靠地面的弹射装置来移动。每个街区都装有弹射装置。使用弹射装置是需要支付一定费用的。而且每个弹射装置都有自己的弹力。设第 i i 行第 j j 列的弹射装置有 Aij A_{ij} 的费用和 Bij B_{ij} 的弹力。并规定有相邻边的格子间距离是 1 1 。那么,任何飞侠都只需要在 (i,j) (i,j) 支付 Aij A_{ij} 的费用就可以任 意选择弹到距离不超过 Bij B_{ij} 的位置了。

    有三个飞侠,分别叫做 X、Y、Z。现在它们决定聚在一起玩,于是想往其中一人的位置集合。告诉你 3 3 个飞侠的坐标,求往哪里集合大家需要花的费用总和最低。

    于  BZOJ, Dijkstra, 安徽集训, 最短路 继续阅读

  5. 差分约束系统学习笔记

    差分约束系统,就是给出一组形如 xixj>=dx_i-x_j>=d 的不等式,求出这组不等式的一组解。这类问题通常转化为图论中的最短路来解。

    于  图论, 学习笔记, 差分约束系统, 最短路, 算法模板 继续阅读