來源：?？途W：

時間限制：C/C++ 1秒，其他語言2秒 空間限制：C/C++ 262144K，其他語言524288K 64bit IO Format: %lld

題目描述

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最多能連續攻擊的次數。
示例1
輸入
復制

3 1 2 3 2 4 5

輸出
復制

2

備注:

對于30% 的數據，保證N≤1000
對于100% 的數據，保證N≤1000000

題解：

方法一：
經典的二分圖匹配
因為每個裝備有兩個屬性，我們必須找到一個與之可以相應匹配的物品，所以我們建立x->i,y->i,兩條邊，然后我們從屬性值1開始從小到大的順序跑匈牙利算法匹配二分圖，當匹配斷開，匹配值就是我們要找的答案
方法二：
每個裝備兩個屬性，相當于兩個點，中間一條線連接，我們將這些邊按照屬性值順序連接在一起，查看哪些點和1在一個連通塊里面，這個連通塊中間有沒有環
樣例：

3 1 2 3 2 4 5

建圖：

流程：
1匹配1
2匹配2
3匹配2，但是2已經被2匹配了，所以（下面的）2改為匹配1，但（上面）1已經被（下面）1匹配，且1無法更改匹配對象，所以此次3匹配2失敗
一旦匹配失敗，直接結束，答案為最后的匹配值

代碼：

#include<bits/stdc++.h> using namespace std; const int maxn=1e6+10; struct node{int v,w,next; }edge[maxn<<1]; int cnt,head[maxn]; int now,use[maxn],match[maxn]; void add(int u,int v){edge[++cnt].next=head[u];edge[cnt].v=v;head[u]=cnt; } bool dfs(int u){for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(use[v]==now)continue;use[v]=now;if(!match[v]||dfs(match[v])){match[v]=u;return 1;}}return 0; } int main() {int n;cin>>n;cnt=0;memset(head,-1,sizeof(head));for(int i=1;i<=n;i++){int x,y;cin>>x>>y;add(x,i);add(y,i);}int ans=0;for(int i=1;i<=10000;i++){now=i;if(dfs(i))ans++;else break;}printf("%d\n",ans);return 0;}

總結

以上是生活随笔為你收集整理的【每日一题】8月14日题目精讲 [SCOI2010]游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。