2017-Personal3-team2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 * B.Yu-Gi-Oh!
   * 调整怪兽和非调整怪兽当做左右两边的点，然后对于每一只同调怪兽p，假设合成其的调整怪兽x和非调整怪兽y，则连x -> y, flow=1,cost=atk[x]+atk[y]-atk[p]的边，具体实现的时候一定要保证处理边和建边都要是O(n^2^)级别的(不然会tle)，可以开一个二维数组记录x和y能达成的最高攻击力同调怪物，然后跑最小费用可行流，用Σatk - 费用就是答案了。
 * D. Asa's Chess Problem
   * 源点向行点和列点连上下界均为黑点个数的边，行点和列点向汇点连上下界为要求黑点个数的边，对于每一个pair，如果颜色不同，行相同就列a向列b连流量为1费用为1的边，列相同就行a向行b连流量为1费用为1的边，跑上下界费用流即可。
 * L. The King’s Problem
   * tarjan把点缩了变成DAG，然后用匈牙利跑最小路径覆盖就可以了。（注意：匈牙利跑最小路径覆盖只限于DAG，原来任意一条边x->y直接当做左边点x向右边点y连边，跑出来最大匹配，然后点数-最大匹配就是最小路径覆盖)。
  • B.Yu-Gi-Oh!
    • 调整怪兽和非调整怪兽当做左右两边的点，然后对于每一只同调怪兽p，假设合成其的调整怪兽x和非调整怪兽y，则连x -> y, flow=1,cost=atk[x]+atk[y]-atk[p]的边，具体实现的时候一定要保证处理边和建边都要是O(n2)级别的(不然会tle)，可以开一个二维数组记录x和y能达成的最高攻击力同调怪物，然后跑最小费用可行流，用Σatk - 费用就是答案了。
  • D. Asa's Chess Problem
    • 源点向行点和列点连上下界均为黑点个数的边，行点和列点向汇点连上下界为要求黑点个数的边，对于每一个pair，如果颜色不同，行相同就列a向列b连流量为1费用为1的边，列相同就行a向行b连流量为1费用为1的边，跑上下界费用流即可。
  • L. The King’s Problem
    • tarjan把点缩了变成DAG，然后用匈牙利跑最小路径覆盖就可以了。（注意：匈牙利跑最小路径覆盖只限于DAG，原来任意一条边x->y直接当做左边点x向右边点y连边，跑出来最大匹配，然后点数-最大匹配就是最小路径覆盖)。