[SCOI2010]连续攻击游戏

题目描述

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

输入输出格式

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

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

输入输出样例

输入样例#1：
3
1 2
3 2
4 5
输出样例#1：
2
说明

Limitation

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

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

表示没想~~不会·~~并查集的做法

作为一个刚刚学完匈牙利算法的蒟蒻，大佬如果觉得写的不好或代码太丑请见谅。
这个题显然可以用二分图做，把装备两个属性分别减一作为两个点向该装备连一条边最后从零开始跑匈牙利，跑到匹配不了为止，这时就可以求出想要的答案

注意到

n<=1000000

为防止TLE 可以使用链式前向星存边，用时间戳优化每次对vis的memset即可

代码如下

# include <stdio.h>
# include <stdlib.h>
# include <iostream>
# include <string.h>
# define N 1000001
# define M 2000001
# define ll long long
# define RG register
# define IL inline
# define UN unsigned
# define mem(a, b) memset(a, b, sizeof(a))
# define min(a, b) ((a) < (b)) ? (a) : (b)
# define max(a, b) ((a) > (b)) ? (a) : (b)
using namespace std;

int n, m, ft[N], nt[M], to[M], cnt, girl[N], vis[N], id;

IL ll Get(){
    char c = '!'; ll z = 1, num = 0;
    while(c != '-' && (c < '0' || c > '9'))
        c = getchar();
    if(c == '-')
        z = -1, c = getchar();
    while(c >= '0' && c <= '9')
        num = num * 10 + c - '0', c = getchar();
    return num * z;
}

IL int Dfs(RG int u){
    for(RG int i = ft[u]; i != -1; i = nt[i]){
        RG int v = to[i];
        if(vis[v] != id){
            vis[v] = id;
            if(girl[v] == -1 || Dfs(girl[v])){
                girl[v] = u;
                return 1;
            }
        }
    }
    return 0;
}

IL int Hungarian(){
    RG int ans = 0;
    for(RG int i = 0; i <= m; i++){
        id++;
        if(Dfs(i)) ans++;
        else return ans;
    }
    return ans;
}

IL void Add(RG int u, RG int v){
    to[cnt] = v; nt[cnt] = ft[u]; ft[u] = cnt++;
}

int main(){
    mem(girl, -1); mem(ft, -1);
    n = Get();
    for(RG int i = 1; i <= n; i++){
        RG int a = Get(), b = Get();
        Add(a - 1, i);
        Add(b - 1, i);
        m = max(m, a - 1);
        m = max(m, b - 1);
    }
    printf("%d
", Hungarian());
    return 0;
}

本人小蒟蒻一个，不起眼的博客，大佬们见笑了。。。

[SCOI2010]连续攻击游戏 匈牙利算法

[SCOI2010]连续攻击游戏

注意到

n<=1000000

[SCOI2010]连续攻击游戏匈牙利算法