bzoj 1854 游戏二分图匹配 || 并查集

2021-11-26 23:18:38

题目链接

Description

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

Input

输入的第一行是一个整数N，表示lxhgww拥有N种装备接下来N行，是对这N种装备的描述，每行2个数字，表示第i种装备的2个属性值

Output

输出一行，包括1个数字，表示lxhgww最多能连续攻击的次数。

Sample Input

Sample Output

HINT

【数据范围】

对于30%的数据，保证N < =1000

对于100%的数据，保证N < =1000000

思路

参考：

http://hzwer.com/2950.html

http://blog.csdn.net/PoPoQQQ/article/details/41544997

法一：二分图最大匹配

思路同bzoj 1911.

将每种武器和它的两种属性连边，因为属性数为\(1e3\)，武器数为\(1e6\)，故用属性去匹配武器，这也符合属性从小到大连续的要求。

注意点，匈牙利算法中每次都要初始化\(used[]\)数组，在这里代价太高，故可用时间戳代替（一开始将时间戳开成了\(bool\)数组玄学到哭泣）。

法二：并查集

十分巧妙。

将武器的属性抽象成点，考虑在同一种武器的两种属性间连边。

如果一个联通块了呈树形结构，且树中节点为\(x\)个，则能从中取\(x-1\)个武器。

方式是每个点分配给它上面的那条边，这样，除了根节点之外的每个点都能分配到一条边。即这些\(x-1\)个属性都能对应到一个武器。

如果不是树形结构，且其中节点为\(x\)个，则能取\(x\)个武器。

因为不是树，所以其中必然有环。那么，给环上的每个点分配它顺时针方向的一条边，给不在环上的点分配靠近环方向的边。这样，每个点都能分配到一条边。即\(x\)个属性每个都能对应到一个武器。

可以考虑用并查集来做。祖先节点为编号最大的节点，其是否可以被选择不确定，其子孙节点都是可以选择的（详见上面讨论的两种情况）。

考虑在\(x\)和\(y\)之间加边，

如果\(x\)的祖先\(fx\)与\(y\)的祖先\(fy\)相同，则说明加出了环，则祖先节点本身也可被选择；

如果不同，则让两个祖先中较小的那个未被选择的能够被选择。

最后从小到大扫描一遍，不连续即停。

小结

两种不同的建图方式，两种做法，都很有启发意义。

Code

Ver. 1

#include <bits/stdc++.h>

#define maxn 10000

#define maxm 1000010

using namespace std;

typedef long long LL;

struct Edge {

    int to, ne;

    Edge(int _to=0, int _ne=0) : to(_to), ne(_ne) {}

}edge[maxm * 2];

int tot, ne[maxm], T, match[maxm], vis[maxm];

void add(int u, int v) {

    edge[tot] = Edge(v, ne[u]);

    ne[u] = tot++;

}

int find(int u) {

    for (int i = ne[u]; ~i; i = edge[i].ne) {

        int v = edge[i].to;

        if (vis[v] != T) {

            vis[v] = T;

            if (!match[v] || find(match[v])) {

                match[v] = u;

                return true;

            }

        }

    }

    return false;

}

int main() {

    int n;

    scanf("%d", &n);

    tot = 0; memset(ne, -1, sizeof(ne));

    for (int i = 0; i < n; ++i) {

        int x, y;

        scanf("%d%d", &x, &y);

        add(x, i), add(y, i);

    }

    int i = 1;

    for (; i <= maxn; ++i) {

        ++T;

        if (!find(i)) break;

    }

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

    return 0;

}

Ver. 2

#include <bits/stdc++.h>

#define maxn 10000

using namespace std;

typedef long long LL;

bool vis[maxn+10];

int fa[maxn+10];

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

int main() {

    int n;

    scanf("%d", &n);

    for (int i = 1; i <= maxn; ++i) fa[i] = i;

    for (int i = 0; i < n; ++i) {

        int x, y;

        scanf("%d%d", &x, &y);

        x = find(x), y = find(y);

        if (x == y) vis[x] = true;

        else {

            if (x > y) swap(x, y);

            if (vis[x]) vis[y] = true;

            else vis[x] = true;

            fa[x] = y;

        }

    }

    int i=1;

    for (; i <= maxn && vis[i]; ++i);

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

    return 0;

}

码农公寓