解題區►解題區 - UVa

UVa 11284 - Shopping Trip

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

宅宅喜歡收集 DVD，居住在編號 0 的地方，移動在街道之間需要成本。現在已知到某些店家可以獲得比網購還便宜的價錢，請問出門的最大獲益為何？

可以選擇經過某些店家而不入門購買，每一家店獲得利益後，不能再次獲得利益。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
4 5
0 1 1.00
1 2 3.00
1 3 2.00
2 4 4.00
3 4 3.25
3
2 1.50
3 7.00
4 9.00
1 1
0 1 1.50
1
1 2.99

Sample Output

1
2
Daniel can save $3.50
Don't leave the house

Solution

街道圖最多 50 個節點，但是能獲得利益的店家最多 12 家，窮舉拜訪順序需要 $O(12!)$ ，但這樣的速度肯定太慢。先將點之間做最短路徑，只把挑選店家的部分抓出，移動花費就從最短路徑中得到。

利用狀態壓縮得到 dp[i][j]，表示已經經過的店家狀態 i、最後一個走訪店家的編號 j，這個狀態的花費就是從編號 0 出發，經過 i 狀態的所有店家，最後停留在 j，接著窮舉下一個店家 k，則 

1
dp[i|(1<<k)][k] = max(dp[i][j] - g[j][k] + profit[k])

g[i][j] 表示編號 i 到編號 j 的花費 (寫的時候注意對應點與壓縮後的編號)。

由於沒必要經過所有的店家，針對每一格狀態都嘗試返回原點 0，得到最大利益。

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
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXN = 64;
int main() {
	int testcase;
	int N, M, P;
	int u, v, a, b;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d", &N, &M);
		
		int g[MAXN][MAXN], profit[MAXN] = {};
		int dp[1<<12][12];
		memset(g, 0x3f, sizeof(g));
		for (int i = 0; i < M; i++) {
			scanf("%d %d %d.%d", &u, &v, &a, &b);
			g[u][v] = min(g[u][v], a * 100 + b);
			g[v][u] = min(g[v][u], a * 100 + b);
		}
		
		scanf("%d", &P);		
		for (int i = 0; i < P; i++) {
			scanf("%d %d.%d", &u, &a, &b);
			profit[u] += a * 100 + b;
		}
		
		// floyd algorithm
		for (int i = 0; i <= N; i++)
			g[i][i] = 0;
		for (int k = 0; k <= N; k++)
			for (int i = 0; i <= N; i++) 
				for (int j = 0; j <= N; j++)
					g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
					
		// get store
		vector<int> S;
		for (int i = 0; i <= N; i++) {
			if (profit[i] > 0)
				S.push_back(i);
		}
		
		// run dp
		vector< pair<int, int> > o;
		for (int i = 0; i < (1<<S.size()); i++) {
			for (int j = 0; j < S.size(); j++)
				dp[i][j] = -0x3f3f3f3f;
			o.push_back(make_pair(__builtin_popcount(i), i));
		}
				
		int ret = -0x3f3f3f3f;
		for (int i = 0; i < S.size(); i++) {
			u = S[i];
			dp[1<<i][i] = -g[0][u] + profit[u];
		}
		
		sort(o.begin(), o.end());
		for (int i = 0; i < o.size(); i++) {
			int state = o[i].second;
			for (int j = 0; j < S.size(); j++) {
				if (dp[state][j] == -0x3f3f3f3f)
					continue;
					
				u = S[j];
				ret = max(ret, dp[state][j] - g[u][0]);
				for (int k = 0; k < S.size(); k++) {
					if ((state>>k)&1)
						continue;
					v = S[k];
					dp[state|(1<<k)][k] = max(dp[state|(1<<k)][k], dp[state][j] - g[u][v] + profit[v]);
				}
			}
		}
		
		if (ret > 0)
			printf("Daniel can save $%d.%02d\n", ret/100, ret%100);
		else
			printf("Don't leave the house\n");
	}
	return 0;
}