Tim's Programming Space |
|
|||
Tim's Programming Space |
日歷
統計
導航常用鏈接留言簿(3)隨筆檔案文章檔案搜索最新評論
閱讀排行榜評論排行榜 |
游戲 【題目描述】 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
|
![]() |
|
Copyright © TimTopCoder | Powered by: 博客園 模板提供:滬江博客 |