首页 > ACM题库 > HDU-杭电 > HDU 3810-Magina-背包问题-[解题报告]HOJ
2015
04-13

HDU 3810-Magina-背包问题-[解题报告]HOJ

Magina

问题描述 :

Magina, also known as Anti-Mage, is a very cool hero in DotA (Defense of the Ancient).
Decrypt coordinate
If you have no idea of him, here is some brief introduction of his legendary antecedents:
Twin sons to the great Prophet, Terrorblade and Magina were blessed with divine powers: Terrorblade granted with an unnatural affinity with life forces; Magina gifted with energy manipulation. Magina’s eventual overexposure to the magic gradually augmented his elemental resistances and bestowed him the unique ability to move faster than light itself. Now, broken by Terrorblade’s fall to the dark side, Magina answers the Sentinel’s call in a desperate bid to redeem his brother. Every bitter strike turns the Scourge’s evil essences upon themselves, culminating in a finale that forces his enemy to awaken to the void within and spontaneously implode.
Magina has a very IMBA (imbalanced) skill �C Blink, yes, move from one place to another place in a wink. Our problem begins at there.
As a formidable hero in the later stage, Magina always farm with the wild monsters for a long time. To make the farming more efficient, Magina use Blink frequently to jump here and there. Here we assume Blink skill has no CD, that is, we can use this skill at any time we want.
There are N spots of the wild monsters, and Magina can choose any one to begin. For every spots, Magina may use Ti time to kill the monsters and gain Gi units money, or he choose blink to other spots, which is known to our brilliant Magina. If the monsters in a spot were killed, it won’t appear any more.
Now Magina want to get M units money to but some excellent equipment, say Battle Fury for example. As a hero to save the world, there is no much time left for Magina, he wonders the minimum time for him to gain at least M units money.

输入:

The first line contains a single integer T, indicating the number of test cases.
Each test case begins with two integers N, M. Their meanings are the same as the description.
Then N blocks follow, each one describes a spot of wild monsters.
The first line of each block is there integers Ti, Gi and Ki. Ti is the time, Gi is the units of money, Ki is the number of spots Magina can blink to from here.
Then Ki integer Cij follow, indicating the spots’ ID Magina can blink to. You may assume no ID would appear twice.
The spots are described with ID increasing from 1 to N. Input ensure if you can blink from i to j, you can also blink from j to i.

Technical Specification

1. 1 <= T <= 50
2. 1 <= N <= 50
3. 1 <= Ti <= 10000000
4. 1 <= M, Gi <= 1000000000
5. 1 <= Ki < N
6. 1 <= Cij <= N

输出:

The first line contains a single integer T, indicating the number of test cases.
Each test case begins with two integers N, M. Their meanings are the same as the description.
Then N blocks follow, each one describes a spot of wild monsters.
The first line of each block is there integers Ti, Gi and Ki. Ti is the time, Gi is the units of money, Ki is the number of spots Magina can blink to from here.
Then Ki integer Cij follow, indicating the spots’ ID Magina can blink to. You may assume no ID would appear twice.
The spots are described with ID increasing from 1 to N. Input ensure if you can blink from i to j, you can also blink from j to i.

Technical Specification

1. 1 <= T <= 50
2. 1 <= N <= 50
3. 1 <= Ti <= 10000000
4. 1 <= M, Gi <= 1000000000
5. 1 <= Ki < N
6. 1 <= Cij <= N

样例输入:

3
1 4
2 5 0
1 5
1 4 0
4 10
1 9 0
3 3 1
3
3 3 2
2 4
4 4 1
3

样例输出:

Case 1: 2
Case 2: Poor Magina, you can't save the world all the time!
Case 3: 10

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3810


题目大意题目源自Dota,前面一堆介绍敌法师,最后一段才开始说有n堆野兽,每堆野兽屠杀完完需要花费ti时间,可以增加金钱gi,敌法师有瞬移技能,可以从某堆野兽移到另一堆野兽,题目有给定从哪堆可以移到哪堆。最后问在满足打的金钱多余m的情况下的最少时间。


解题思路2011年武汉邀请赛网络赛的金牌题,题目看上去很复杂,又是n堆野兽,又是各种瞬移。但是理清楚之后就发现这是题背包题,先把能够相连的野兽堆用深搜找出来归为一组,然后我们要做的就是在这组里面选择0,1,…num[tot]堆进行屠杀,每堆野兽有两种选择:杀获不杀.这样问题就转为求tot组01背包。

     但本题的金钱和屠杀时间范围都特别大,屠杀时间的范围是1-1000万,金钱的范围是1-10亿,不能用常规的两重循环模拟。其实用两个优先队列就可以模拟01背包的计算过程,第一次将(0,0)入队,然后出队转移到下一个状态,转移完这两个状态都进入队列,可以用两个优先队列进行操作,一个表示上一轮的计算结果,一个是这一轮,就相当于滚动数组。在用优先队列模拟的过程中要注意剪枝,如果不剪或者剪得不好就是MLE。我试了好几种剪枝,只有一种可以,那就是在每次转移完要把队列1复制到队列2的时候,判断下入队的这个点是不是满足价值比前面入队的点金钱少且耗时少,如果不是,这个肯定比如前面入队的那个优。比如,(6,4)表示打到钱为6,且耗时4,如果下一个要进队的是(5,5),那肯定是前面的更优,对吧?就是这样。

    这题还因为输出不可能的情况时少写了++Cas导致Wa了几次。由于前面一直MLE,后面Wa,认为是算法的问题,一直检查算法。我想这种情况在现场赛也可能碰到,现在碰到了是好事,小心驶得万年船,谨以为戒。

   按我这样写比iSea的标程快了15倍,第一榜第一位,剪得够强够有力,得瑟下。    


测试数据:


10
3 9
3 3 2
2 3
3 3 2
1 3
3 3 2
1 2

3 3
3 3 2
2 3
5 3 2
1 3
4 3 2
1 2

1 4
2 5 0

1 5
1 4 0

4 10
1 9 0
3 3 1
3
3 3 2
2 4
4 4 1
3

代码:

#include <stdio.h>
#include <string.h>
#include <queue>
#include <string.h>
using namespace std;
#define MIN 52
#define INF 1000000000
#define int64 __int64


struct node {

    int64 t,val;
    friend int operator < (node a,node b) {

		if (a.val == b.val)
			return a.t > b.t;
		else
			return a.val < b.val;
    }
}arr[MIN],now,next;
priority_queue<node> qu1,qu2;
int n,m,maze[MIN][MIN],vis[MIN];
int gtot,num[MIN],group[MIN][MIN];


void Dfs(int i) {

    vis[i] = 1;
    int j = ++num[gtot];
    group[gtot][j] = i;
    for (int k = 1; k <= n; ++k)
        if (!vis[k] && maze[i][k]) Dfs(k);
}
void DivideGroup() {

    int i,j,k;
    for (gtot = i = 1; i <= n; ++i)
        if (!vis[i]) Dfs(i),gtot++;
}
int64 Solve_1A() {

    int i,j,k;
    int64 minn,tpk,tpval;
    minn = INF;        //时间最多为1000万 * 50 == 5亿,用10亿够大了


    for (i = 1; i < gtot; ++i) {
    //模拟01背包
        while (!qu1.empty()) qu1.pop();
        while (!qu2.empty()) qu2.pop();
        now.t = now.val = 0;
        qu1.push(now);


        for (j = 1; j <= num[i]; ++j) {

            k = group[i][j];        //group存的是第几堆野兽
            while (!qu1.empty()) {

                now = qu1.top();
				qu1.pop(),qu2.push(now);
				next.t = now.t + arr[k].t;
                next.val = now.val + arr[k].val;
                   

                if (next.val >= m) {

                    if (next.t < minn) minn = next.t;
                    continue;
                }
				if (next.t >= minn) continue;
				qu2.push(next);
            }


			tpk = INF;
            while (!qu2.empty()) {
					
                now = qu2.top(),qu2.pop();
                if (tpk >= now.t) qu1.push(now),tpk = now.t;//前面的val大时间也要大,如果后面出队的时间更多,那就要剪掉
            }
        }
    }
    return minn == INF ? -1 : minn;
}


int main()
{
    int i,j,t,cas = 0;
    int u,v,k;


    scanf("%d",&t);
    while (t--) {

        scanf("%d%d",&n,&m);
        memset(maze,0,sizeof(maze));
        memset(vis,0,sizeof(vis));
        memset(num,0,sizeof(num));
        for (i = 1; i <= n; ++i) {

            scanf("%d%d%d",&arr[i].t,&arr[i].val,&k);
            while (k--) {

                scanf("%d",&u);
                maze[i][u] = 1;
            }
        }


        DivideGroup();   //能够相互连接的算一堆
        int64 ans = Solve_1A();
        if (ans != -1) printf("Case %d: %I64d\n",++cas,ans);
        else printf("Case %d: Poor Magina, you can't save the world all the time!\n",++cas);
    }
}

文ZeroClock原创,但可以转载,因为我们是兄弟。

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/woshi250hua/article/details/7609293


  1. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。