题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1： 

3
1 2
3 2
4 5

输出样例#1： 

2

说明

对于的数据，保证

对于的数据，保证

来源：SCOI 2010

思路：

二分图的最大匹配问题，做法很巧妙，但是很难想到。

第一眼看到这个题想到的是将某个物品的两个属性分成左右部点，但是很难解决本题，尤其是在处理一个物品只能用一种属性的时候。所以我们不妨换一种思路，对于物品i的属性 ，分别从和向连一条有向边。将物品的属性当做左部点，编号当做右部点，求最大匹配即可。

这样为什么是正确的呢？我们可以考虑匈牙利算法的具体过程：在匹配值为i的技能时，那么到的属性肯定已经匹配完成，所以如果对应的编号被匹配了的话，那么就让匹配的那个属性再去找别的物品标号匹配，形象地说，就是用别的物品来释放攻击力为的这个技能，用这个物品释放攻击力为i的技能。如果找到这样一条增广路，那么就说明当前可以匹配，。

代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
#define maxn 1000007
using namespace std;
int n,link[maxn],num,head[maxn],zrj,maxx;
bool vis[maxn];
inline int qread() {
  char c=getchar();int num=0,f=1;
  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
  for(;isdigit(c);c=getchar()) num=num*10+c-'0';
  return num*f;
}
struct node {
  int v,nxt;
}e[maxn<<1];
inline void ct(int u, int v) {
  e[++num].v=v;
  e[num].nxt=head[u];
  head[u]=num;
}
bool dfs(int u) {
  for(int i=head[u];i;i=e[i].nxt) {
    int v=e[i].v;
    if(!vis[v]) {
      vis[v]=1;
      if(!link[v]||dfs(link[v])) {
        link[v]=u;
        return 1;
      }
    }
  }
  return 0;
}
int main() {
  n=qread();
  for(int i=1,u,v;i<=n;++i) {
    u=qread(),v=qread();
    ct(u,i),ct(v,i);
    maxx=max(maxx,max(u,v));
  }
  for(int i=1;i<=maxx;++i) {
    memset(vis,0,sizeof(vis));
    if(dfs(i)) ++zrj;
    else break;
  }
  printf("%d\n",zrj);
  return 0;
}