【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[];

int stot, h[];

void add(int u, int v) {

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

    h[u] = stot;

}

int vis[], to[], 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 ;

            }

        }

    }

    return ;

}

int main() {

    scanf("%d", &n);

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

        int x, y;

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

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

    }

    int i;

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

        ++ idc;

        if(!find(i))    break;

    }

    printf("%d", i - );

    return ;

}