题目描述

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

输入输出格式

输入格式：

输入的第一行是一个整数N，表示lxhgww拥有N种装备接下来N行，是对这N种装备的描述，每行2个数字，表示第i种装备的2个属性值

输出格式：

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

输入输出样例

输入样例#1： 

31 23 24 5

输出样例#1： 

2

说明

Limitation

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

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

来源：SCOI 2010

 

Solution:

　　高考三天假，一题没有刷。。。果然$6$月注定假多刷题少`～`

　　本题是一道剖析算法本质的题目，我们发现每一个物品严格的只能和一种属性搭配，很容易想到二分图最大匹配，分析下时间复杂度，首先匈牙利算法最坏复杂度是$O(n^2)$，题目中保证属性不超过$10000$，所以理论可以过。

　　那么考虑建图，直接每个物品连向属性，显然不行，无法判断属性的连续性，我们此时想到每次是从前往后增广，所以可以换过来，每种属性向物品连边，注意只要连有向边就好了，因为每次用的属性既然要连续，那么意味着用过的属性不能再用了（我们是用属性在与物品匹配），这样就避免了左右集合点重复的情况。

　　实现时就从前往后枚举属性，当前属性无法增广时，因为属性不可能连续了所以就跳出循环，否则一直往后增广并累计答案。

代码：

 

#include
      
       #define il inline#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)using namespace std;const int N=1000105;int n,ans,h[N],cnt,to[N<<1],net[N<<1],match[N],vis[10005],tot;il int gi(){    int a=0;char x=getchar();    while(x<'0'||x>'9')x=getchar();    while(x>='0'&&x<='9')a=(a<<3)+(a<<1)+x-48,x=getchar();    return a;}il void add(int u,int v){to[++cnt]=v,net[cnt]=h[u],h[u]=cnt;}il bool check(int u){    for(int i=h[u];i;i=net[i]){        int v=to[i];        if(vis[v]<=tot){            vis[v]=tot+1;            if(!match[v]||check(match[v])){match[v]=u;return 1;}        }    }    return 0;}int main(){    n=gi();    int u,v,m=0;    For(i,1,n)u=gi(),v=gi(),add(u,i),add(v,i);    For(i,1,10000){        if(check(i))ans++;        else break;        tot++;    }    cout<