poj3539 Elevator——同余类bfs

题目：http://poj.org/problem?id=3539

题目大意是给定 a, b, c，求 1~h 内有多少个数可以被 a, b, c 通过加减法组成；

这是今天刚讲的神奇的——同余类 bfs 问题！

大概就是选定一个模数，就选最小的(常数可能会比较小？)，不妨令作 a，构建一系列点，组成 mod a 剩余系；

然后我们要找到每个点的最小可达数，然后它加上若干个 a 就都是可达的；

对于一个点 x，它可以转移到 (x + b) % b，代价是 b ；c 同理；

从起点开始 bfs，对于本题来说就是1%a，且 dis[1%a] = 1(层数)，求出 dis[] 数组，就是每个点的最小可达数；

计算答案就是对于每个余数(点)，看看在1~h 中有多少个它加若干 a 可达的数，也就是 (h - dis[x]) / a + 1；

不过其实不 bfs 也可以，反正就是求最短路；

注意 dis 是 long long 哟~

代码如下：

dijkstra：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

typedef long long ll;

int const maxn=1e5+;

ll h,ans,dis[maxn];

int a,b,c,hd[maxn],ct;

priority_queue<pair<ll,int> >q;

bool vis[maxn];

struct N{

    int to,nxt,w;

    N(int t=,int n=,int w=):to(t),nxt(n),w(w) {}

}ed[maxn<<];

void add(int x,int y,int z){ed[++ct]=N(y,hd[x],z); hd[x]=ct;}

void dijkstra()

{

    memset(dis,0x3f,sizeof dis);

    dis[%a]=; q.push(make_pair(-,%a));

    while(q.size())

    {

        int x=q.top().second; q.pop();

        if(vis[x])continue;

        vis[x]=;

        for(int i=hd[x];i;i=ed[i].nxt)

        {

            int u=ed[i].to;

            if(dis[u]>dis[x]+ed[i].w)

            {

                dis[u]=dis[x]+ed[i].w;

                q.push(make_pair(-dis[u],u));

            }

        }

    }

}

int main()

{

    scanf("%lld%d%d%d",&h,&a,&b,&c);

    if(a>b)swap(a,b); if(a>c)swap(a,c);

    for(int i=;i<a;i++)

    {

        add(i,(i+b)%a,b);

        add(i,(i+c)%a,c);

    }

    dijkstra();

    for(int i=;i<a;i++)

    {

        if(dis[i]>h)continue;//!

        ans+=(ll)(h-dis[i])/a+;

    }

    printf("%lld\n",ans);

    return ;

}

dijkstra

spfa：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

typedef long long ll;

int const maxn=1e5+;

ll h,ans,dis[maxn];

int a,b,c,hd[maxn],ct;

queue<int>q;

bool vis[maxn];

struct N{

    int to,nxt,w;

    N(int t=,int n=,int w=):to(t),nxt(n),w(w) {}

}ed[maxn<<];

void add(int x,int y,int z){ed[++ct]=N(y,hd[x],z); hd[x]=ct;}

void spfa()

{

    memset(dis,0x3f,sizeof dis);

    dis[%a]=; q.push(%a); vis[%a]=;

    while(q.size())

    {

        int x=q.front(); q.pop(); vis[x]=;

        for(int i=hd[x];i;i=ed[i].nxt)

        {

            int u=ed[i].to;

            if(dis[u]>dis[x]+ed[i].w)

            {

                dis[u]=dis[x]+ed[i].w;

                if(!vis[u])vis[u]=,q.push(u);

            }

        }

    }

}

int main()

{

    scanf("%lld%d%d%d",&h,&a,&b,&c);

    if(a>b)swap(a,b); if(a>c)swap(a,c);

    for(int i=;i<a;i++)

    {

        add(i,(i+b)%a,b);

        add(i,(i+c)%a,c);

    }

    spfa();

    for(int i=;i<a;i++)

    {

        if(dis[i]>h)continue;//!

        ans+=(ll)(h-dis[i])/a+;

    }

    printf("%lld\n",ans);

    return ;

}

spfa

bfs：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

typedef long long ll;

int const maxn=1e5+;

ll h,ans;

ll a,b,c,dis[maxn];//ll

queue<int>q;

bool vis[maxn];

void bfs()

{

    memset(dis,0x3f,sizeof dis);

    dis[%a]=; q.push(%a); vis[%a]=;

    while(q.size())

    {

        int x=q.front(),u; q.pop(); vis[x]=;

        if(dis[u=(x+b)%a]>dis[x]+b)

        {

            dis[u]=dis[x]+b;

            if(!vis[u])/*vis[u]=1,*/q.push(u);

        }

        if(dis[u=(x+c)%a]>dis[x]+c)

        {

            dis[u]=dis[x]+c;

            if(!vis[u])/*vis[u]=1,*/q.push(u);

        }

    }

}

int main()

{

    scanf("%lld%lld%lld%lld",&h,&a,&b,&c);

    if(a>b)swap(a,b); if(a>c)swap(a,c);

    bfs();

    for(int i=;i<a;i++)

    {

        if(dis[i]>h)continue;//!

        ans+=(h-dis[i])/a+;

    }

    printf("%lld\n",ans);

    return ;

}