【BZOJ】1854: [Scoi2010]游戏【二分图】

1854: [Scoi2010]游戏

Time Limit: 5 Sec Memory Limit: 162 MB
Submit: 6759 Solved: 2812
[Submit][Status][Discuss]

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

3
1 2
3 2
4 5

Sample Output

HINT

【数据范围】
对于30%的数据，保证N < =1000
对于100%的数据，保证N < =1000000

Solution

一开始想二分图是在属性之间连边，发现根本不可做啊！

然而正解非常巧妙了！在属性和武器之间连边，每次按顺序去看属性是否可以找到匹配（因为每个武器只能用一次），直到找不到匹配即可。

Code

#include<bits/stdc++.h>
using namespace std;

int n;

struct Node {
    int v, nex;
} Edge[2000005];

int stot, h[1000005];
void add(int u, int v) {
    Edge[++stot] = (Node) {v, h[u]};
    h[u] = stot;
}

int vis[1000005], to[1000005], idc;
bool find(int u) {
    for(int i = h[u]; i; i = Edge[i].nex) {
        int v = Edge[i].v;
        if(vis[v] != idc) {
            vis[v] = idc;
            if(!to[v] || find(to[v])) {
                to[v] = u;
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, i);    add(y, i);
    }
    int i;
    for(i = 1; i <= 10000; i ++) {
        ++ idc;
        if(!find(i))    break;
    }
    printf("%d", i - 1);
    return 0;
}