解題區/解題區 - 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;
}