题目地址：洛谷：【P1640】[SCOI2010]连续攻击游戏 – 洛谷、BZOJ：Problem 1854. — [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
来源：SCOI 2010

题解

对装备和属性的值分别建点，从两个属性的值向装备连有向边，跑匈牙利算法匹配即可，注意我们枚举属性的值的时候，遇到某个值无法被匹配，则直接返回答案，因为要求连续攻击。
n很大，vis数组memset会TLE，我们可以换种方法，使用vis时间戳，每次dfs使用不同的时间戳就可以达到vis的效果。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 1010005;

int n;

struct Edge {
    int to, nxt;
} gra[MAXN << 1];
int head[MAXN], tot;

inline void addedge(int u, int v) {
    gra[tot] = Edge {v, head[u]}; head[u] = tot++;
}

int vis[MAXN];
int match[MAXN];

inline bool dfs(int u, int clk) {
    for(int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(vis[v] != clk) {
            vis[v] = clk;
            if(match[v] == -1 || dfs(match[v], clk)) {
                match[v] = u; match[u] = v; return true;
            }
        }
    }
    return false;
}

inline int bmatch() {
    int res = 0;
    memset(match, -1, sizeof(match));
    for(int i = 1; i <= 10000; i++) {
        if(match[i] == -1) {
            if(dfs(i, i)) res++;
            else break;
        }
    }
    return res;
}

int a, b;

int main() {
    memset(head, -1, sizeof(head));
    n = readint();
    for(int i = 1; i <= n; i++) {
        a = readint(); b = readint();
        addedge(a, i + 10000);
        addedge(b, i + 10000);
    }
    printf("%d", bmatch());
    return 0;
}