BZOJ-1854 游戏 二分图匹配 （并查集）

1854: [Scoi2010]游戏

Time Limit: 5 Sec Memory Limit: 162 MB

Submit: 3372 Solved: 1244

[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

2

HINT

【数据范围】

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

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

Source

Day1

在一片文章中看到的，说是网络流经典建图，然而我还真没想出应该怎么建，但看后发现好像可以二分图匹配乱搞啊，于是打了个匈牙利上去，开始一直RE，调试不爽后一搜题解，这个题竟然可以用并查集？！（果然我沙茶）

感觉是一个比较基本的二分图吧，一直匹配到不能匹配为止

似乎数据范围不能用memset呢，时间戳大法万岁！~\(≧▽≦)/~

此处安利hzwer学长的并查集做法：http://hzwer.com/2950.html

code：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

struct data{

    int next,to;

}edge[2010000];

int head[1001001],cnt=1;

int part[1001001],state[1001001];

int n,t,ans;

void add(int u,int v)

{

    cnt++;

    edge[cnt].next=head[u];

    head[u]=cnt;

    edge[cnt].to=v;

}

bool find(int x)

{

    for (int i=head[x]; i; i=edge[i].next)

        {

            if (state[edge[i].to]==t) continue;

            state[edge[i].to]=t;

            if (!part[edge[i].to] || find(part[edge[i].to]))

                {

                    part[edge[i].to]=x;

                    return true;

                }

        }

    return false;

}

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);

        }

    for (int i=1; i<=10001; i++)

        {

            ++t;

            if (!find(i))

                {ans=i-1;break;}

        }

    printf("%d\n",ans);

    return 0;

}