首页 > 搜索 > BFS搜索 > HDU 4784-Dinner Coming Soon-BFS-[解题报告]HOJ
2015
09-18

HDU 4784-Dinner Coming Soon-BFS-[解题报告]HOJ

Dinner Coming Soon

问题描述 :

  Coach Pang loves his boyfriend Uncle Yang very much. Today is Uncle Yang’s birthday, Coach Pang wants to have a romantic candlelit dinner at Uncle Yang’s house and he has to arrive there in T minutes.
  There are N houses in their city numbered from 1 to N. Coach Pang lives in house 1 while Uncle Yang lives in house N. The houses are connected byM directed roads. It takes some time and usually a fee to pass one road. Coach Pang wants to reach Uncle Yang’s house before the dinner starts with as much money as possible.
  But the matter is not so simple. Coach Pang decides to do some salt trade on the way to Uncle Yang’s house. The host of each house offers a price of a bag of salt, so Coach Pang can make a profit from the price differences. Each time when Coach Pang arrives at a house (except the house 1 and the house N). He can buy one bag of salt, sell one bag of salt or do nothing. Coach Pang can carry at most B bags of salt with him, and he carries no salt when he leaves his house. The trading is so efficient that the time cost of trading can be ignored.
  However, the problem is more complicated than imagine. Coach Pang has a handheld device that can perform a journey around K parallel universes numbered from 0 to K-1. Coach Pang lives in the universe 0. When Coach Pang uses the device in universe i, he will be transported to the same place and the same time of universe (i+1) modK. The host of the house at the same place in different universe may offer a different price of salt. Luckily, the time cost and fee of the city roads are uniform among the K universes. The journey between universes costs no time but Coach Pang has to stand still watching the ads on the device for one minute every time before the device works. Remember, Coach Pang should never visit house 1 or house N in a universe other than universe 0, because the situation might become uncontrollable if he bumps into himself or his boyfriend in another universe.
  The time is running out. Coach Pang asks you to tell him whether he can arrive at Uncle Yang’s house in time, and how much money Coach Pang can have at most when the dinner starts. Coach Pang has R yuan at the start, and will end his journey immediately once he arrives at Uncle Yang’s house. He must arrive at Uncle Yang’s house in T minutes, and he can’t have negative amount of money anywhere anytime. Please help him!

输入:

  The first line of the input is an integer C representing the number of test cases.
  For each test case, the first line will contain 6 integers N, M, B, K, R, T, as described above.
  (2 <= N <= 100, 0 <= M <= 200, 1 <= B <= 4, 2 <= K <= 5, 0 <= R <= 105, 0 <= T <= 200)
  The following K lines contain N integers each, indicating the price pij (0 <= i < K, 1 <= j <= N) for a bag of salt offered by the host of house j in the universe i. The price of house 1 and house N will be marked as -1.(1 <= pij <= 100)
  Then M lines follow, each contains 4 integers a, b, t and m, indicating that there is a road from house a to house b that costs t minutes of time and m yuan of money. (1 <= a,b <= N, a<> b, 1 <= t <=15, 0 <= m <= 100)

输出:

  The first line of the input is an integer C representing the number of test cases.
  For each test case, the first line will contain 6 integers N, M, B, K, R, T, as described above.
  (2 <= N <= 100, 0 <= M <= 200, 1 <= B <= 4, 2 <= K <= 5, 0 <= R <= 105, 0 <= T <= 200)
  The following K lines contain N integers each, indicating the price pij (0 <= i < K, 1 <= j <= N) for a bag of salt offered by the host of house j in the universe i. The price of house 1 and house N will be marked as -1.(1 <= pij <= 100)
  Then M lines follow, each contains 4 integers a, b, t and m, indicating that there is a road from house a to house b that costs t minutes of time and m yuan of money. (1 <= a,b <= N, a<> b, 1 <= t <=15, 0 <= m <= 100)

样例输入:

2
3 2 1 2 10 6
-1 1 -1
-1 5 -1
1 2 1 0
2 3 1 1
2 2 1 2 5 5
-1 -1
-1 -1
1 2 10 2
1 2 2 10

样例输出:

Case #1: 17
Case #2: Forever Alone

        在k个平行空间中,n个点,由m条有向边连接起来,每条边有一个时间花费和金钱花费,同时,在每个点上,可以跳转到(ki+1)%k 的空间里,不同空间的边权值不变。另外,在每到达某个空间的某个顶点时,可以买一包盐,卖一包盐,或者什么也不做,买卖的时间不考虑。相同的顶点在不同的空间中盐的价格也不一定相同..现在给定顶点数n,边数m,盐的最大携带量b,空间数k,初始的金钱r,规定的时间t,问怎么走可以在t时间内从1到达n,并且使到达n时身上的金钱尽可能大。初始时身上一包盐也没有,并且只有在空间0的时候,才能访问顶点1和n,并且一旦到达顶点n,这个过程就要结束……

        很绕口的题目= =….读清楚题意的话首先很容易想到spfa..现场赛的时候估计时间空间给的比较宽松,的确有队伍用spfa过了,但也有被卡常数的..hdoj上spfa估计就不太好过了..时间卡的太近。我是直接写了一个bfs,记录dp【id】【b】【k】【t】,表示在顶点id,身上有b包盐,空间k,还剩t分钟的时间时,身上最多能有多少钱,刚开始写spfa,需要反复的进出队列,所以很悲剧的TLE了。要控制每个状态进出队列一次,又发现有些状态明明可以取得一个更大的值-,但它之前已经被一个小的值占用了-然后我就直接把队列换成了个优先队列,按剩余时间的大小从大到下向下扩展状态,这样就可以保证bfs进行的时候,一定是按时间来一层一层扩展的,并且可以保证在从当前状态开始扩展之前,当前的状态一定是最优的。另外还有一个小坑-不知道是我别的地方写毁了还是怎么回事-..每次跳转空间或者是走到新的顶点时,如果目标点的dp值需要更新,显然需要根据更新后的值来扩展买,卖,不买不卖三种新的状态,但是如果目标点的值不需要更新,我依然需要按这个“不是目标状态最优的值”来扩展买,卖,不买不卖三种状态。举个例子
当前状态如果是2 2 0 25 下一步可以到达 2 2 1 24 然后卖掉一包盐扩展出 2 1 1 24,因为已经卖了一包盐了,他不可以再扩展出2 0 1 24.然后到达2 1 0 25的时候,下一步到达2 1 1 24发现这么走到2 1 1 24没有它当前的钱多,但这个不是最优的状态却可以继续扩展出2 0 1 24这个状态的最优值,所以在这就算得到的不是最优的钱数,我们依然需要往下扩展一下…然后就AC了……

      

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <memory.h>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
using namespace std;
typedef long long ll;
bool vis[105][6][6][202];
int g[105][6][6][202];
int n,m,b,r,k,t,numtt;
int trade[105][6];
inline int getint() {
    char c = getchar();
    int t = 0;
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        t = t * 10 + c - '0';
        c = getchar();
    }
    return t;
}
struct Edge
{
    int v,wt,wm,next;
}edge[202];
int ge[105];
struct sta
{
    int id,b,k,t;
    sta(){};
    sta(int x1,int x2,int x3,int x4)
    {
        id=x1;
        b=x2;
        k=x3;
        t=x4;
    }
//    bool operator>(const sta& s1)const
//    {
//
//        return t>s1.t;
//    }

    bool operator<(const sta& s1)const
    {
        return t<s1.t;
    }
};
int en;

void bfs()
{
    memset(vis,false,sizeof vis);
    memset(g,-1,sizeof g);
    priority_queue<sta> q;
    vis[1][0][0][t]=true;
    g[1][0][0][t]=r;
    q.push(sta(1,0,0,t));
    while(!q.empty())
    {
        sta now=q.top();
        sta tmp=now;
        q.pop();

//        vis[now.id][now.b][now.k][now.t]=false;
        int tid=now.id,tb=now.b,tk=now.k,tt=now.t;
        int fee;
        if (tt>0 && tid!=n && tid!=1)
        {
            tk++;
            if (tk==k) tk=0;
            tt--;
            if (g[tid][tb][tk][tt]<g[now.id][now.b][now.k][now.t])
            {
                g[tid][tb][tk][tt]=g[now.id][now.b][now.k][now.t];
                if (!vis[tid][tb][tk][tt])
                {
                    q.push(sta(tid,tb,tk,tt));
                    vis[tid][tb][tk][tt]=true;
                }
            }
                int ttk=tk,ttid=tid,ttb=tb,ttt=tt;
                fee=g[now.id][now.b][now.k][now.t];

                if (fee>=trade[ttid][ttk] && ttb<b)
                {
                    fee-=trade[ttid][ttk];
                    ttb++;
                    if (g[ttid][ttb][ttk][ttt]<fee)
                    {
                        g[ttid][ttb][ttk][ttt]=fee;
                        if (!vis[ttid][ttb][ttk][ttt])
                        {
                            q.push(sta(ttid,ttb,ttk,ttt));
                            vis[ttid][ttb][ttk][ttt]=true;
                        }
                    }
                }
                ttk=tk; ttid=tid; ttb=tb; ttt=tt;
                fee=g[now.id][now.b][now.k][now.t];
                if (ttb>0)
                {
                    fee+=trade[ttid][ttk];
                    ttb--;
                    if (g[ttid][ttb][ttk][ttt]<fee)
                    {
                        g[ttid][ttb][ttk][ttt]=fee;
                        if (!vis[ttid][ttb][ttk][ttt])
                        {
                            q.push(sta(ttid,ttb,ttk,ttt));
                            vis[ttid][ttb][ttk][ttt]=true;
                        }
                    }
                }


        }
        for (int j=ge[now.id]; j!=-1; j=edge[j].next)
        {
            tid=now.id;
            tb=now.b;
            tk=now.k;
            tt=now.t;
            fee=g[tid][tb][tk][tt];
            int u=now.id;
            int v;
            if (fee>=edge[j].wm && tt>=edge[j].wt)
            {
                v=edge[j].v;
                if ((v==1 || v==n) && tk!=0) continue;

                fee-=edge[j].wm;
                tt-=edge[j].wt;

                if (g[v][tb][tk][tt]<fee)
                {
                    g[v][tb][tk][tt]=fee;
                    if (!vis[v][tb][tk][tt] && v!=n)
                    {
                        q.push(sta(v,tb,tk,tt));
                        vis[v][tb][tk][tt]=true;
                    }
                }
                    if (v!=n && v!=1)
                    {
                        int ttk=tk,ttid=v,ttb=tb,ttt=tt;
                        fee=g[now.id][now.b][now.k][now.t]-edge[j].wm;
                        if (fee>=trade[v][tk] && ttb<b)
                        {
                            fee-=trade[v][tk];
                            ttb++;
                            if (g[ttid][ttb][ttk][ttt]<fee)
                            {
                                g[ttid][ttb][ttk][ttt]=fee;
                                if (!vis[ttid][ttb][ttk][ttt])
                                {
                                    q.push(sta(ttid,ttb,ttk,ttt));
                                    vis[ttid][ttb][ttk][ttt]=true;
                                }
                            }
                        }

                        ttb=tb;
                        fee=g[now.id][now.b][now.k][now.t]-edge[j].wm;

                        if (ttb>0)
                        {
                            fee+=trade[v][tk];
                            ttb--;
                            if (g[v][ttb][ttk][ttt]<fee)
                            {
                                g[v][ttb][ttk][ttt]=fee;
                                if (!vis[v][ttb][ttk][ttt])
                                {
                                    q.push(sta(v,ttb,ttk,ttt));
                                    vis[v][ttb][ttk][ttt]=true;
                                }
                            }
                        }

                    }

            }
        }
    }

}
int main()
{
//    freopen("in.txt","r",stdin);

//    scanf("%d",&numtt);
    numtt=getint();
    for (int ii=1; ii<=numtt; ii++)
    {
        memset(ge,-1,sizeof ge);
//        scanf("%d%d%d%d%d%d",&n,&m,&b,&k,&r,&t);
        n=getint(); m=getint();b=getint(); k=getint(); r=getint(); t=getint();

        for (int i=0; i<k; i++)
         for (int j=1; j<=n; j++)
//         scanf("%d",&trade[j][i]);
            trade[j][i]=getint();

        int x,y,z1,z2;
        en=0;
        for (int i=1; i<=m; i++)
        {
//            scanf("%d%d%d%d",&x,&y,&z1,&z2);
            x=getint(); y=getint(); z1=getint(); z2=getint();
            edge[en].v=y;
            edge[en].wt=z1;
            edge[en].wm=z2;
            edge[en].next=ge[x];
            ge[x]=en;
            en++;

        }
        bfs();
        int ans=-1;
       printf("Case #%d: ",ii);
        for (int i=0; i<=t; i++)
         for (int j=0; j<=b; j++)
         ans=max(ans,g[n][j][0][i]);
        if (ans>=0) printf("%d\n",ans);
        else puts("Forever Alone");

    }
    return 0;
}

参考:http://blog.csdn.net/night_raven/article/details/16439395