Mincost Network Flow
1

2017

1

Problem 合怪升级,每只怪有他的等级和攻击力,以及是否为 tuner monster. 合怪必须一只 tuner monster 与一只 non-tuner monster 合,并且他们的等级之和必须等于合成的怪。只有特定等级和攻击力的怪可以被合成。某些合成怪必须用特定的某一只或某两只怪才能合成。 Solution 看懂题目后建图跑网络流。主要难点在建图。 将 tuner monster(t1) 连到源点,将 non-tuner monster(t2) 连到汇点, capacity 均为 1, cost 均为0。并且列举将该怪与所有另一种怪的组合,以合成等级为索引保存。注意最大等级上限为12,超过12的组合直接 pass 掉。 然后处理合成怪。在合成怪对应等级中搜索对应满足条件的组合,加入到 t1, t2 矩阵中。这里有一个必须搞的优化,就是只选攻击力最大且大于两只被合成怪的合成怪,对满足的 t1,t2 连 capacity 为 1, cost 为 t1 攻击力 加 t2 攻