[BZOJ1854]&&[Scoi2010] 游戏

描述 Description

lxhgww 最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有 2 个属性,这些属性的值用 [1,10000] 之间的数表示。当他使用某种装备时,他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。 游戏进行到最后,lxhgww 遇到了终极 boss,这个终极 boss 很奇怪,攻击他的装备所使用的属性值必须从 1 开始连续递增地攻击,才能对 boss 产生伤害。也就是说一开始的时候,lxhgww 只能使用某个属性值为 1 的装备攻击 boss,然后只能使用某个属性值为 2 的装备攻击 boss,然后只能使用某个属性值为 3 的装备攻击 boss…… 以此类推。 现在 lxhgww 想知道他最多能连续攻击 boss 多少次?

输入格式 InputFormat

输入的第一行是一个整数 N,表示 lxhgww 拥有 N 种装备。

接下来 N 行,是对这 N 种装备的描述,每行 2 个数字,表示第 i 种装备的 2 个属性值

输出格式 OutputFormat

输出一行,包括 1 个数字,表示 lxhgww 最多能连续攻击的次数。

样例输入 SampleInput

3
1 2
3 2
4 5

样例输出 SampleOutput

2


BZOJ 1854


很明显的二分图匹配,输出连续能匹配多少个点。

学会了一种新的匈牙利模板 %>_<%

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=1000005;
int i,j,t,n,m,l,r,k,z,y,x;
struct edge
{
    int to,nx;
}e[maxn*2];
int head[maxn],match[maxn],used[maxn];
int mat,cnt;
inline void ins(int u,int v)
{
    e[++cnt].to=v;e[cnt].nx=head[u];
    head[u]=cnt;
}
bool crosspath(int s,int now)
{
    int i,v;
    for (i=head[s];i;i=e[i].nx)
    {
        v=e[i].to;
        if (used[v]!=now)
        {
            used[v]=now;
            if (!match[v] || crosspath(match[v],now))
            {
                match[v]=s;
                return true;
            }
        }
    }
    return false;
}
inline void hungary()
{
    int i,j,t;
    memset(match,0,sizeof(match));
    memset(used,0,sizeof(used));
    for (i=1;i<=m;i++)
    {
        if (crosspath(i,i)) mat++;
        else break;
    }
}
int main()
{
    cnt=mat=0;
    m=0;
    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%d%d",&x,&y),ins(x,i),ins(y,i),m=max(m,x),m=max(m,y);
    hungary();
    printf("%d\n",mat);
    return 0;
}