hdu 3810 Magina 敌法师 优先队列式分支限界法求解01背包

缘起

【1】中说过了， 01背包有三种解法——dp、深搜+剪枝、分支限界. 【1】和【2】已经展示了前两种解法. 本文展示第三种解法. 而第三种使用的队列一般是FIFO队列或者优先队列. 本文展示的是优先队列.

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
敌法师是DOTA中受人欢迎的打野英雄. 为了让打野更有效率，敌法师经常使用Blink技能（我们假设该技能没有CD时
间）来回穿梭于各个野怪点. 假设有N个野怪点. 敌法师选择其中任何一个开始打野. 对于每个野怪点，敌法师使用Ti时间
杀掉野怪并获取Gi金钱. 一个地方的野怪如果被杀掉则不会再出现了. 现在我们的敌法师想获取M金钱买装备. 但是我们的
敌法师没有太多时间，所以我们需要计算敌法师获取M金钱的最短时间.

【输入】
多样例，第一行是样例数目T. 每个样例开始于两个正整数N和M,然后就是N行，每行有三个整数Ti, Gi, Ki, 其中Ki是敌法师可以从当前野怪点blink到几个其他的野怪点. 然后就是Ki个整数 Cij. 输入假设如果敌法师可以从i野怪点blink到野怪点j, 则亦可以从j blink回 i.
输入的范围是
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

【限制】
Time limit 30000 ms
Memory limit 32768 kB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
//#define LOCAL
const int inf = ~0u>>1; // 最大int, 骚写法

int n,m,cnt; // n是野怪点数, m是敌法师需要的金钱,cnt是连通分支的个数
bool map[55][55],vist[55]; // 无向图,map[i][j]=true 表示敌法师可以从野怪点i blink到 j, vist[i]表示i这个野怪点是否访问过了

struct Node // 优先队列中的节点
{
	int c,w; // 该节点的价值（即金钱）和时间
	Node(int c, int w):c(c),w(w){}
	bool operator <(const Node &b) const
	{
		return w==b.w?c>b.c:w<b.w; // 如果金钱相等,则时间长的优先低, 反之金钱高的优先级高
	}
};

priority_queue<Node> pq1,pq2; // 两个用于分支限界的队列, 具体过程就是pq1剪枝之后倒到pq2中去, 然后pq2中再次剪枝之后才倒回pq1中去, pq1才是主战场,pq2 是中转站

struct Monster
{
	int c,w;  // 打这处的野怪需要耗费c的时间, 但是获得w的金钱
}monsters[55]; // 野怪点

vector<Monster> g[55]; // 连通分支

typedef vector<Monster>::iterator mit;

void dfs(int i)
{
	vist[i] = true;
	g[cnt].push_back(monsters[i]); // 收集第cnt个连通分支
	for (int j = 1;j<=n;j++)
	{
		if (!vist[j] && map[i][j])
		{
			dfs(j);
		}
	}
}

void divide()
{
	for (int i = 1; i<=n;i++)
	{
		g[i].clear();
	}
	cnt = 0;
	for (int i = 1; i<=n; i++)
	{
		if (!vist[i])
		{
			cnt++; //连通分支数+1
			dfs(i); // 开始去获取第cnt个连通分支（起始于i号野怪点）
		}
	}
}

int sz() // 使用优先队列式分支限界法求解01背包问题
{
	int ret = inf;
	for (int i = 1; i<= cnt; i++) // 只需要在各个连通分支上取最小即可
	{
		while(!pq1.empty())pq1.pop();
		while(!pq2.empty())pq2.pop(); // 开始考察第i个连通分支g[i], 首先清空pq1、pq2这两个优先队列
		Node s(0,0); // 不放任何物品, 金钱为0
		pq1.push(s);
		for (mit j = g[i].begin(); j!=g[i].end(); j++) // 考虑逐个加入g[i]这个连通分支中的物品
		{
			while(!pq1.empty())
			{
				Node s = pq1.top();
				pq1.pop(); // 队首出堆
				pq2.push(s); // 不放置当前物品,则金钱和耗费都不会增加
				s.c+=j->c;
				s.w+=j->w; // 考虑放当前物品
				if (s.w>=m) // 如果当前节点已经满足了要求,则s不需要再进队了（纵使后面金钱可能更多, 但不需要）,剪枝了,剪枝点1
				{
					if (s.c<ret) // 更新ret
					{
						ret = s.c;
					}
					continue;
				}
				if (s.c>=ret) // 如果节点的耗费大于当前最优, 但是因为pq是按照金钱出堆的, 所以当前节点的金钱一定少于之前某个节点, 则s就不需要开拓了，剪枝了,剪枝点2
				{
					continue;
				}
				pq2.push(s);
			}
			int tmp = inf; // pq2中的节点（都是pq1中的节点开辟出来的）别急着倒回pq1, 还要进行剪枝呢! 这里剪枝的手段是让pq2中的节点互相厮杀
			while(!pq2.empty())
			{
				Node s = pq2.top();
				pq2.pop();
				if (s.c<tmp)
				{
					tmp = s.c;
					pq1.push(s);
				} // 对于 s.c>=tmp的, 也不需要继续开拓了, 理由同剪枝点2, 这里发生了剪枝——剪枝点3
			}
		}
	}
	return ret;
}

int main() 
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int t;
	scanf("%d", &t);
	for (int i = 1; i<=t; i++)
	{
		scanf("%d%d", &n,&m); // 野怪点数目, 敌法师需要的金钱
		memset(map, 0, sizeof(map));
		memset(vist, 0, sizeof(vist));
		for (int j =  1,k,x; j<=n; j++) // 读取n个野怪点的数据
		{
			scanf("%d%d%d", &monsters[j].c, &monsters[j].w, &k);
			while(k--) // 读取k个当前野怪点可以blink到的点
			{
				scanf("%d", &x);
				map[j][x] = map[x][j] = true;
			}
		} // 至此, 一个case的数据全部读取完毕
		divide(); // dfs划分无向图的连通分支（因为敌法师只能在一个连通分支中blink）
		int ans;
		if ((ans=sz())==inf)
		{
			printf("Case %d: Poor Magina, you can't save the world all the time!\n", i);
		}
		else
		{
			printf("Case %d: %d\n", i, ans);
		}
	}
	return 0;
}

上面要是没有3个剪枝点的话, 会MLE

ac情况

Status Accepted
Time 31ms
Memory 1768kB
Length 2955
Lang C++
Submitted 2019-08-19 10:47:13
Shared
RemoteRunId 30341535

参考

【1】https://yfsyfs.github.io/2019/08/18/poj-3172-Scales-01%E8%83%8C%E5%8C%85-%E6%B7%B1%E6%90%9C-%E5%89%AA%E6%9E%9D/

【2】https://yfsyfs.github.io/2019/08/18/%E7%99%BE%E7%BB%83oj-2773-%E9%87%87%E8%8D%AF-01%E8%83%8C%E5%8C%85/