游戏
【题目描述】
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最多能连续攻击的次数。
【样例输入】
3
1 2
3 2
4 5
【样例输出】
2
【数据范围】
对于30%的数据，保证N<=1000
对于100%的数据，保证N<=1000000
===========================================================================
没什么说的，匈牙利最坏10000^2过了。。其实对于这样随机的边很多的图。。匈牙利的实际运行时间比O(n)多不了多少。。实际测试表明。。比用下面方法的要快。。囧。
官方题解是：10000个点，1000000条边的一个图。对于每个联通块如果是树则只能选到n-1个，那么肯定是选最小的n-1个，如果有环则全部可以。最后for下从1开始哪些可以就行了。。
吐槽：。。。考完回来写匈牙利，写了两遍都错了，而且错的一样。。。调了很久才发现写错的地方，杯具。。
1 #include <iostream>
2 #define MAXN 1000010
3 #define MAXM MAXN*2
4
5 using namespace std;
6
7 int Count = 0;
8 int begin[MAXN+1], end[MAXM+1], next[MAXM+1];
9 void AddEdge(int a, int b){
10 Count++;
11 next[Count] = begin[a];
12 begin[a] = Count;
13 end[Count] = b;
14 }
15
16 int n;
17 #define BUFSIZE 1000000*10
18 char buf[BUFSIZE], *pt = buf;
19 #define scan_int(x) \
20 { \
21 x = 0; \
22 while (!((*pt) >= '0' && (*pt) <= '9')) pt++; \
23 while (((*pt) >= '0' && (*pt) <= '9')) x = x * 10 + (*(pt++)) - '0'; \
24 }
25 void Init(){
26 scanf("%d",&n);
27 int a,b;
28 fread(pt, 1, BUFSIZE, stdin);
29 for (int i = 1; i<=n; i++){
30 //scanf("%d%d",&a,&b);
31 scan_int(a); scan_int(b);
32 AddEdge(a,i);
33 AddEdge(b,i);
34 }
35 }
36
37 int cnt;
38 int q[MAXN+1];
39 bool hash[MAXN+1];
40 int Link[MAXN+1];
41 bool dfs(int x){
42 for (int now = begin[x]; now; now = next[now])
43 if (!hash[end[now]]){
44 hash[end[now]] = true;
45 q[++cnt] = end[now];
46 if (!Link[end[now]] || dfs(Link[end[now]])){
47 Link[end[now]] = x;
48 return true;
49 }
50 }
51 return false;
52 }
53
54 void Solve(){
55 int Ans;
56 for (int i = 1; i<=10001; i++){
57 cnt = 0;
58 if (!dfs(i)){
59 Ans = i-1;
60 break;
61 }
62 for (int j = 1; j<=cnt; j++)
63 hash[q[j]] = false;
64 }
65 printf("%d\n",Ans);
66 }
67
68 int main(){
69 freopen("game.in","r",stdin);
70 freopen("game.out","w",stdout);
71 Init();
72 Solve();
73 return 0;
74 }
75