游戲
【題目描述】
lxhgww最近迷上了一款游戲，在游戲里，他擁有很多的裝備，每種裝備都有2個(gè)屬性，這些屬性的值用[1,10000]之間的數(shù)表示。當(dāng)他使用某種裝備時(shí)，他只能使用該裝備的某一個(gè)屬性。并且每種裝備最多只能使用一次。
游戲進(jìn)行到最后，lxhgww遇到了終極boss，這個(gè)終極boss很奇怪，攻擊他的裝備所使用的屬性值必須從1開始連續(xù)遞增地攻擊，才能對boss產(chǎn)生傷害。也就是說一開始的時(shí)候，lxhgww只能使用某個(gè)屬性值為1的裝備攻擊boss，然后只能使用某個(gè)屬性值為2的裝備攻擊boss，然后只能使用某個(gè)屬性值為3的裝備攻擊boss……以此類推。
現(xiàn)在lxhgww想知道他最多能連續(xù)攻擊boss多少次？
【輸入】
輸入的第一行是一個(gè)整數(shù)N，表示lxhgww擁有N種裝備
接下來N行，是對這N種裝備的描述，每行2個(gè)數(shù)字，表示第i種裝備的2個(gè)屬性值
【輸出】
輸出一行，包括1個(gè)數(shù)字，表示lxhgww最多能連續(xù)攻擊的次數(shù)。
【樣例輸入】
3
1 2
3 2
4 5
【樣例輸出】
2
【數(shù)據(jù)范圍】
對于30%的數(shù)據(jù)，保證N<=1000
對于100%的數(shù)據(jù)，保證N<=1000000
===========================================================================
沒什么說的，匈牙利最壞10000^2過了。。其實(shí)對于這樣隨機(jī)的邊很多的圖。。匈牙利的實(shí)際運(yùn)行時(shí)間比O(n)多不了多少。。實(shí)際測試表明。。比用下面方法的要快。。囧。
官方題解是：10000個(gè)點(diǎn)，1000000條邊的一個(gè)圖。對于每個(gè)聯(lián)通塊如果是樹則只能選到n-1個(gè)，那么肯定是選最小的n-1個(gè)，如果有環(huán)則全部可以。最后for下從1開始哪些可以就行了。。
吐槽：。。。考完回來寫匈牙利，寫了兩遍都錯(cuò)了，而且錯(cuò)的一樣。。。調(diào)了很久才發(fā)現(xiàn)寫錯(cuò)的地方，杯具。。
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