Treasure Map Gym – 101617J(BFS+剪枝)

题目链接:https://cn.vjudge.net/problem/Gym-101617J
题目大意:有一些矿和一些双向路,通过双向路需要花费时间,而矿的产出每天会递减少,问从一点除法最多可以收集多少矿物
解题思路:BFS+剪枝
一晚上的wa7,到最后也没想明白是怎么回事,结果第二天早上在路上突然就想懂了
原wa代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct node
{
    int val,jian;
}d[1010];
struct nodee
{
    long long w;
    int v,t,next;
    bool operator < (const nodee &r)const
    {
        return t>r.t;
    }
}edge[5020];
int n,m;
int head[1010];
int maxday,cnt;
long long dis[1010];
long long ans;
priority_queue<nodee>q;
void bfs(int s)
{
    memset(dis,0,sizeof(dis));
    nodee add;
    add.v=s;
    add.t=0;
    add.w=d[s].val;
    dis[s]=add.w;
    q.push(add);
    nodee tmp;
    while(!q.empty())
    {
        tmp=q.top();
        q.pop();
        ans=max(ans,tmp.w);
        if(tmp.t>maxday)
        {
            return;
        }
        for(int i=head[tmp.v];i!=-1;i=edge[i].next)
        {
            long long w;
            int t;
            t=tmp.t+edge[i].t;
            w=d[edge[i].v].val-t*(d[edge[i].v].jian);
            if(w<0)w=0;
            w=w+tmp.w;
            if(w>=dis[edge[i].v])
            {
                dis[edge[i].v]=w;
                add.t=t;
                add.v=edge[i].v;
                add.w=w;
                q.push(add);
            }
        }
    }
}

void addedge(int u,int v,int w)
{
    edge[cnt].v=v;
    edge[cnt].t=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(head,-1,sizeof(head));
    maxday=0;
    cnt=0;
    ans=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&d[i].val,&d[i].jian);
        maxday=max(maxday,(int)ceil(d[i].val*1.0/d[i].jian));
    }
    int u,v,w;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w);
        addedge(v,u,w);
    }
    bfs(1);
    printf("%lld\n",ans);
    return 0;
}

看上去没有什么问题,但其实问题挺大,本来的设想是通过dis数组,因为出对顺序是按照时间顺序递增出队的,所以如果同一个点到达了多次,如果后到的价值没有大于前面到的时候的价值,就不进行更新和入队了。但是问题在于,我们判断的点并不是出队的那个点,而是出队的点往后走的点,因为之前的设想成立的前提是按时间顺序增序判断,而不同的路所需的时间是不同的,因此无法保证要判断的点是按时间顺序的,代码也就错了。
解决方案是,把一维的dis数组改成二维的,第二维是时间,这样就变成了,同一个点如果在同样的时间到达,以前的价值比当前的大的话就不入队,剪枝的效果差了很多但是起码不会mle和wa了。
ac代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct node
{
    int val,jian;
}d[1010];
struct nodee
{
    int w;
    int v,t,next;
    bool operator < (const nodee &r)const
    {
        return t>r.t;
    }
}edge[5020];
int n,m;
int head[1010];
int maxday,cnt;
int dis[1010][1010];
int ans;
priority_queue<nodee>q;
void bfs(int s)
{
    memset(dis,0,sizeof(dis));
    nodee add;
    add.v=s;
    add.t=0;
    add.w=d[s].val;
    dis[s][0]=add.w;
    q.push(add);
    nodee tmp;
    while(!q.empty())
    {
        tmp=q.top();
        q.pop();
        ans=max(ans,tmp.w);
        if(tmp.t>maxday)
        {
            return;
        }
        for(int i=head[tmp.v];i!=-1;i=edge[i].next)
        {
            long long w;
            int t;
            t=tmp.t+edge[i].t;
            w=d[edge[i].v].val-t*(d[edge[i].v].jian);
            if(w<0)w=0;
            w=w+tmp.w;
            if(w>dis[edge[i].v][t])
            {
                dis[edge[i].v][t]=w;
                add.t=t;
                add.v=edge[i].v;
                add.w=w;
                q.push(add);
            }
        }
    }
}

void addedge(int u,int v,int w)
{
    edge[cnt].v=v;
    edge[cnt].t=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(head,-1,sizeof(head));
    maxday=0;
    cnt=0;
    ans=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&d[i].val,&d[i].jian);
        maxday=max(maxday,(int)ceil(d[i].val*1.0/d[i].jian));
    }
    int u,v,w;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w);
        addedge(v,u,w);
    }
    bfs(1);
    printf("%d\n",ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注