Menci

眉眼如初,岁月如故

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


  1. 「POJ 2728」Desert King - 01 分数规划

    一个王国有 N N 个城市,每个城市有坐标 (x,y) (x, y) 和海拔 z z ,在 N N 个城市之间修水渠,要保证每个城市有水,水渠是水平的,每个城市的海拔不同,现在要求修单位长度的水渠的海拔高度差最小。

    于  POJ, Prim, 二分答案, 分数规划, 实数二分, 生成树 继续阅读

  2. 「SDOI2015」星际战争 - 网络流

    Y 军团一共派遣了 N N 个巨型机器人进攻 X 军团的阵地,其中第 i i 个巨型机器人的装甲值为 Ai A_i 。当一个巨型机器人的装甲值减少到 0 或者以下时,这个巨型机器人就被摧毁了。X 军团有 M M 个激光武器,其中第 i i 个激光武器每秒可以削减一个巨型机器人 Bi B_i 的装甲值。激光武器的攻击是连续的。这种激光武器非常奇怪,一个激光武器只能攻击一些特定的敌人。Y 军团需要知道 X 军团最少需要用多长时间才能将 Y 军团的所有巨型机器人摧毁。

    于  BZOJ, Dinic, SDOI, 二分答案, 图论, 实数二分, 网络流 继续阅读