elementlz  
日历
<2010年4月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678
统计
  • 随笔 - 2
  • 文章 - 0
  • 评论 - 0
  • 引用 - 0

导航

常用链接

留言簿

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

 
lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示。当他使用某种装备时,他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。
游戏进行到最后,lxhgww遇到了终极boss,这个终极boss很奇怪,攻击他的装备所使用的属性值必须从1开始连续递增地攻击,才能对boss产生伤害。也就是说一开始的时候,lxhgww只能使用某个属性值为1的装备攻击boss,然后只能使用某个属性值为2的装备攻击boss,然后只能使用某个属性值为3的装备攻击boss……以此类推。
现在lxhgww想知道他最多能连续攻击boss多少次?
对于30%的数据,保证N<=1000
对于100%的数据,保证N<=1000000
#include<iostream>
#define MAXM 1000001
#define MAXN 1000001
#define MAXNANS 10000
using namespace std;
int a,b,n,tot,Tnow[MAXM],Ty[MAXM],pre[MAXM];
int head;
int from[MAXN];
bool visit[MAXN];
int Happen[MAXN];
bool find(int x){
    int mark = Tnow[x];
    while (mark > 0)
        {
            if (!visit[Ty[mark]])
                {
                    visit[Ty[mark]] = true;
                    Happen[++head] = Ty[mark];
                    if ((!from[Ty[mark]]) || (find(from[Ty[mark]])))
                        {
                            from[Ty[mark]] = x;
                            return true;
                        }
                }
            mark = pre[mark];
        }
    return false;
    }
void cnt(int x,int y){
     tot++;
     pre[tot] = Tnow[x];
     Tnow[x] = tot;
     Ty[tot] = y;
}
int main(){
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    cin>>n;
    tot = 0;
    for (int i=1;i<=n;i++)
        {
            cin>>a>>b;
            cnt(a,i+MAXNANS);
            cnt(b,i+MAXNANS);
        }
    int Answer ;
    memset(visit,false,sizeof(visit));
    for (int i=1;i<=n;i++)
        {
            head = 0;
            if (!find(i))
            {
                    Answer = i - 1;
                    break;
                }
            for (int i=1;i<=head;i++)
                visit[Happen[i]] = false;
        }
    printf("%d\n",Answer);
    return 0;
}

posted on 2010-04-15 13:31 EleMenTLz 阅读(157) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


 
Copyright © EleMenTLz Powered by: 博客园 模板提供:沪江博客