Mayflyyh
Mayflyyh
MayFlyyh's Blog
Luogu P1640 [SCOI2010]连续攻击游戏

Luogu P1640 [SCOI2010]连续攻击游戏

题目描述

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<bits/stdc++.h>
const int N = 3010000;
struct edge{
    int next,to;
}e[N];
int cnt,v[N],tim,n,f[N],last[N];
void add(int a,int b){
    cnt++;
    e[cnt].next=last[a],last[a]=cnt;
    e[cnt].to=b;
}
bool find(int x){
    for(int i=last[x];i;i=e[i].next){
        if(v[e[i].to]==tim) continue;
        v[e[i].to]=tim;
        if(!f[e[i].to]||find(f[e[i].to])){
            f[e[i].to]=x;
            return 1;
        }
    }
    return 0;
}
int main(){
    //freopen("game.in","r",stdin);
    //freopen("game.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int x,y;
        scanf("%d %d",&x,&y);
        add(x,10000+i);
        add(y,10000+i);
    }
    for(int i=1;i<=10001;++i){
        tim++;
        if(!find(i)){
            printf("%d\n",i-1);
            return 0;
        }
    }
}

可以把武器当边,然后连接两个数值,如果连成的集合是一棵树,那么就有n-1个点可以使用,如果是环就都可以。那把数值大的设为树根,尽量先用数值小的。

#include<bits/stdc++.h>
const int N = 1e6+1e4;
int n,fa[N],v[N];
int find(int x){
    return !fa[x]?x:fa[x]=find(fa[x]); 
}
int main(){
    std::cin>>n;
    while(n--){
        int a,b;
        std::cin>>a>>b;
        int t1=find(a),t2=find(b);
        if(t1==t2){
            v[std::max(a,b)]=1;
            continue;
        }
        if(t1<t2) std::swap(a,b),std::swap(t1,t2);
        fa[t2]=t1;
        v[b]=1;
    }
    for(int i=1;i<=10001;++i){
        if(find(i)==i&&!v[i]){
            printf("%d",i-1);
            return 0;
        }
    }
    return 0;
}
本文链接:http://www.mayflyyh.com/archives/447
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
首页      并查集      Luogu P1640 [SCOI2010]连续攻击游戏
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

MayFlyyh's Blog

Luogu P1640 [SCOI2010]连续攻击游戏
Luogu P1640 [SCOI2010]连续攻击游戏 题目描述 lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示。当他使用…
扫描二维码继续阅读
2018-12-19