Menci

眉眼如初,岁月如故

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


  1. 「JSOI2009」游戏 - 博弈 + 二分图匹配

    N×M N \times M 的迷宫中有一个棋子,AA 首先任意选择棋子放置的位置。然后,YY 和 AA 轮流将棋子移动到相邻的格子里。

    游戏的规则规定,在一次游戏中,同一个格子不能进入两次,且不能将棋子移动到某些格子中去。当玩家无法继续移动棋子时,游戏结束,最后一个移动棋子的玩家赢得了游戏。

    求 AA 初始将棋子放在哪些格子会有必胜策略。

    于  BZOJ, Dinic, JSOI, 二分图匹配, 博弈, 网络流 继续阅读

  2. 「SCOI2015」小凸玩矩阵 - 二分图匹配

    小方给小凸一个 NM N * M NM N \leq M )的矩阵 A A ,要求小秃从其中选出 N N 个数,其中任意两个数字不能在同一行或同一列,现小凸想知道选出来的 N N 个数中第 K K 大的数字的最小值是多少。

    于  BZOJ, Dinic, SCOI, 二分图匹配, 二分答案, 安徽集训, 网络流 继续阅读

  3. 「SCOI2010」游戏 - 二分图匹配

    在游戏里,他拥有很多的装备,每种装备都有两个属性,这些属性的值用 [1,10000] [1, 10000] 之间的数表示。当他使用某种装备时,他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。 终极 BOSS 很奇怪,攻击他的装备所使用的属性值必须从 1 1 开始连续递增地攻击,才能对 BOSS 产生伤害。也就是说一开始的时候,只能使用某个属性值为 1 1 的装备攻击 BOSS,然后只能使用某个属性值为 2 2 的装备攻击 BOSS,然后只能使用某个属性值为 3 3 的装备攻击 BOSS …… 以此类推。他最多能连续攻击 BOSS 多少次?

    于  BZOJ, SCOI, 二分图匹配, 匈牙利算法, 图论, 枚举答案 继续阅读

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

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

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

  5. 「COGS 728」最小路径覆盖问题 - 二分图匹配

    给定有向图 G=(V,E)G=(V,E) 。设 P 是 G 的一个简单路(顶点不相交)的集合。如果 V 中每个顶点恰好在 P 的一条路上,则称 P 是 G 的一个路径覆盖。P 中路径可以从 V 的任何一个顶点开始,长度也是任意的,特别地,可以为 0。G 的最小路径覆盖是 G 的所含路径条数最少的路径覆盖。

    设计一个有效算法求一个有向无环图 G 的最小路径覆盖。

    于  COGS, Dinic, 二分图匹配, 图论, 网络流, 网络流 24 题 继续阅读

  6. 「COGS 14」搭配飞行员 - 二分图匹配

    从一个二分图中选出尽量多的边,使得任意两条边没有公共点。

    于  COGS, Dinic, 二分图匹配, 图论, 网络流, 网络流 24 题 继续阅读