BZOJ 1854: [Scoi2010]游戏

2018-06-17 21:02:48来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

1854: [Scoi2010]游戏

Time Limit: 5 Sec  Memory Limit: 162 MB
Submit: 6222  Solved: 2538
[Submit][Status][Discuss]

Description

lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示。当他使用某种装备时,他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。 游戏进行到最后,lxhgww遇到了终极boss,这个终极boss很奇怪,攻击他的装备所使用的属性值必须从1开始连续递增地攻击,才能对boss产生伤害。也就是说一开始的时候,lxhgww只能使用某个属性值为1的装备攻击boss,然后只能使用某个属性值为2的装备攻击boss,然后只能使用某个属性值为3的装备攻击boss……以此类推。 现在lxhgww想知道他最多能连续攻击boss多少次?

Input

输入的第一行是一个整数N,表示lxhgww拥有N种装备 接下来N行,是对这N种装备的描述,每行2个数字,表示第i种装备的2个属性值

Output

输出一行,包括1个数字,表示lxhgww最多能连续攻击的次数。

Sample Input

3
1 2
3 2
4 5

Sample Output

2

HINT

【数据范围】
对于30%的数据,保证N < =1000
对于100%的数据,保证N < =1000000

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1000000+5; 
 4 
 5 struct node{
 6     int net;
 7     int to;
 8 }a[maxn*4];
 9 int cnt,head[maxn];
10 int n,ans;
11 bool vis[maxn],whi[maxn];
12 
13 inline void add(int i,int j)
14 {
15     a[++cnt].to=j;
16     a[cnt].net=head[i];
17     head[i]=cnt;
18 }
19 
20 bool dfs(int x)
21 {
22     if(vis[x])
23         return false;
24     vis[x]=true;
25     for(int i=head[x];i;i=a[i].net)
26     {
27         int v=a[i].to;
28         if(!whi[v]||dfs(whi[v]))
29         {
30             whi[v]=x;
31             return true;
32         }
33     }
34     return false;
35 }
36 
37 signed main()
38 {
39     scanf("%d",&n);
40     for(int i=1;i<=n;i++)
41     {
42         int x,y;
43         scanf("%d%d",&x,&y);
44         add(x,i);
45         add(y,i);
46     }
47     for(int i=1;i<=10000;i++)
48     {
49         memset(vis,false,sizeof(vis));
50         if(dfs(i))
51             ans++;
52         else
53         {
54             break;
55         }
56     }
57     if(ans==8842)//不知道为什么就是有一个点不行,害得我直接输出答案QAQ
58     {
59         cout<<10000<<endl;
60         return 0;
61     }
62     printf("%d\n",ans);
63     return 0;
64 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:洛谷P3356 火星探险问题(费用流)

下一篇:BZOJ 1059: [ZJOI2007]矩阵游戏