「SCOI2010」游戏 - 二分图匹配

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

链接

BZOJ 1854

题解

看一下数据范围 ，如果枚举每件武器，肯定要 的算法才能过，但又想不出 的算法来 ……

我们换一种思路，从属性值小到大，之间如果有一个数不能没有可用的武器，则不可能继续打出比这个数更大的属性值了。也就是说答案具有单调性，可以采用枚举答案并检验的方法。

题目中并没有要求某个属性值要由特定的武器打出，所以说可以任意选择某个可用的武器来打出指定的属性值。

从 开始，任选一个可打出 的武器并标记为使用过，枚举时如果发现能打出 的武器全部被用过了，就尝试将某一件属性值为 武器标记为 ，并寻找 的替代（），这样递归下去，直到某个属性值使用了一件没有被使用武器，则成功，否则失败。

算法思想与『二分图匹配』中的匈牙利算法比较相似。

代码

#include <cstdio>
#include <vector>

const int MAXN = 1000000;
const int MAXX = 10000;

struct Gun {
    int x[2];
    int selected;

    Gun() : selected(-1) {}

    void select(int x) {
        if (this->x[0] == x) selected = 0;
        else selected = 1;
    }
} guns[MAXN];

int n;
std::vector<int> gunID[MAXX];

inline bool check(int x, int ignore = -1) {
    for (std::vector<int>::const_iterator p = gunID[x].begin(); p != gunID[x].end(); p++) {
        Gun &g = guns[*p];
        if (g.selected == -1) {
            g.select(x);
            return true;
        }
    }

    for (std::vector<int>::const_iterator p = gunID[x].begin(); p != gunID[x].end(); p++) {
        if (*p == ignore) continue;

        Gun &g = guns[*p];
        if (check(g.x[g.selected ^ 1], *p)) {
            g.select(x);
            return true;
        }
    }

    return false;
}

int main() {
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        Gun &g = guns[i];

        scanf("%d %d", &g.x[0], &g.x[1]), g.x[0]--, g.x[1]--;

        gunID[g.x[0]].push_back(i);
        gunID[g.x[1]].push_back(i);
    }

    int i;
    for (i = 0; i < MAXX; i++) {
        if (!check(i)) break;
    }

    printf("%d\n", i);

    return 0;
}