【每日一题】8月14日题目精讲 [SCOI2010]游戏

来源：牛客网：

时间限制：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]游戏的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。