P1640 [SCOI2010]连续攻击游戏:(二分图)

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

输入:
3
1 2
3 2
4 5
输出：
2

初次看的时候，想用装备建图模型，可以接在连续用的装备建一条边，然后这个模型似乎不太适用于二分图，当时想了一个有向图最长路的解法（未实现），但不能访问过去已经访问过的点，而新的起点又要把前面的标记清0，觉得不好下手，遂放弃。

仔细读题，发现攻击值的范围只有10000，想到一个模型，用装备连边到攻击数值，开一个1000000的容器用来存装备，建边，要保证1一定被匹配，但发现好像不太能保证1一定被匹配，且匹配不一定是连续的。

反过来，用数值建边到装备，因为匈牙利算法是一个连续的过程，我们从1开始匹配，如果能找到装备可以匹配就匹配，如果找不到了，就直接break。这是正解模型

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+10;
int n,x,y,used[100 * maxn],cy[100 * maxn];
vector<int> g[maxn];
int find(int u){
 	for(int i = 0; i < g[u].size(); i++){
  		int v = g[u][i];
  		if(!used[v]){
   			used[v] = 1;
   			if(!cy[v] || find(v)){
    				cy[v] = u;
    				return 1;
   			}
  		}
 	}
 	return 0;
}
int match(){
 	int res = 0;
 	for(int i = 1; i <= 10000; i++){
  		if(find(i)) res++;
  		else break;
 	}
 	return res;
}
int main(){
 	scanf("%d",&n);
 	for(int i = 1; i <= n; i++){
  		scanf("%d%d",&x,&y);
  		g[x].push_back(i);
  		g[y].push_back(i);
 	}
 	printf("%d\n",match());
 	return 0;
}