欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【BZOJ1854】[Scoi2010]游戏 二分图最大匹配

程序员文章站 2022-05-22 13:35:45
...

【BZOJ1854】[Scoi2010]游戏

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

题解:由于边数很少,所以可以使用二分图最大匹配,但每次匹配是都memset一下时间复杂度会变成O(n^2),于是我们要采用黑科技

平常我们将vis初值清零,访问到这个点的时候就令vis[]=1,而我们可以令在第i次匹配的时候就令vis[]=i,这样所有vis不是i的点就是没有访问过的,这样就大大节省了时间复杂度

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=1000010;
int n,cnt,ans;
int vis[maxn],from[maxn],to[maxn<<1],next[maxn<<1],val[maxn<<1],head[maxn];
void add(int a,int b)
{
    to[cnt]=b;
    next[cnt]=head[a];
    head[a]=cnt++;
}
int dfs(int x)
{
    int i;
    for(i=head[x];i!=-1;i=next[i])
    {
        if(vis[to[i]]==ans)    continue;
        vis[to[i]]=ans;
        if(!from[to[i]]||dfs(from[to[i]]))
        {
            from[to[i]]=x;
            return 1;
        }
    }
    return 0;
}
int main()
{
    scanf("%d",&n);
    int i,a,b;
    memset(head,-1,sizeof(head));
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&a,&b);
        add(a,i),add(b,i);
    }
    for(ans=1;ans<=n;ans++)
    {
        if(!dfs(ans))
        {
            printf("%d",ans-1);
            return 0;
        }
    }
    printf("%d",n);
    return 0;
}