#333. 【NOIP2017】宝藏

1、错误的$n^42^n$做法：

dp[s]表示当前的点集为s，然后从这些点中选一个做起点i，然后枚举边，然后更新dp[t|(1<<j)]。dis[s][i]表示点集为s的情况下的i号点的深度。详见代码。

为什么是错的，不满足当前最优一定是最后最优。比如下面的hack数据，正确答案应该是10420，即从4号点出发，长度为1的那条边不要。而在上面的dp中，点集为234的状态中只能从24和34转移而来，而这两个取最小值的时候，一定会算上1这条边，答案为12，而不是10这条边。导致下一步dp的时候，深度边长，导致更不优。

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<iostream>
  4 #include<cstring>
  5 #include<cctype>
  6 #include<cmath>
  7 #include<set>
  8 #include<queue>
  9 #include<vector>
 10 #include<map>
 11 #include<bitset>
 12 using namespace std;
 13 typedef long long LL;
 14 
 15 //char buf[100000], *p1 = buf, *p2 = buf;
 16 //#define nc() p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++
 17 
 18 inline int read() {
 19     int x = 0, f = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch=='-') f = -1;
 20     for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0'; return x * f;
 21 }
 22 
 23 const int N = 100;
 24 const LL LLINF = 1e18;
 25 const int INF = 1e9;
 26 
 27 LL dp[(1 << 12) + 10];
 28 int mp[N][N], dis[(1 << 12) + 10][15];
 29 int n, m;
 30 
 31 LL solve(int x) {
 32     memset(dis, 0, sizeof(dis));
 33     int S = (1 << n) - 1;
 34     
 35     for (int s = 0; s <= S; ++s) dp[s] = LLINF;
 36     dis[1 << x][x] = 1, dp[1 << x] = 0;
 37     
 38     for (int s = 0, t; s <= S; ++s) { // 点集 
 39         if (dp[s] == LLINF) continue;
 40         cout << bitset<6>(s) << "
";
 41         for (int i = 0; i < n; ++i) { // 选一个点当起点 
 42             if (!((s >> i) & 1)) continue;
 43             for (int j = 0; j < n; ++j) { // 到达的下一个点 
 44                 if (i == j || mp[i][j] == INF || ((s >> j) & 1)) continue;
 45                 t = s | (1 << j);
 46                 cout << bitset<6>(t) << "
";
 47                 if (dp[t] > dp[s] + dis[s][i] * mp[i][j]) {
 48                     dp[t] = dp[s] + dis[s][i] * mp[i][j];
 49                     for (int k = 0; k < n; ++k) dis[t][k] = dis[s][k];
 50                     dis[t][j] = dis[s][i] + 1;
 51                     cout << dp[t] << "
";
 52                 }
 53             }
 54         }
 55     }
 56     return dp[S];    
 57 }
 58 
 59 int main() {
 60 //    freopen("1.txt", "r", stdin);
 61 //    freopen("2.txt", "w", stdout);
 62     n = read(), m = read();
 63     
 64     for (int i = 0; i <= n; ++i) 
 65         for (int j = 0; j <= n; ++j) mp[i][j] = INF;
 66     for (int i = 1; i <= m; ++i) {
 67         int u = read() - 1, v = read() - 1, w = read();
 68         mp[u][v] = min(mp[u][v], w), mp[v][u] = min(mp[v][u], w);
 69     }
 70     
 71     LL ans = 1e18;
 72     for (int i = 0; i < n; ++i) 
 73         ans = min(ans, solve(i));
 74     cout << ans;
 75     
 76     return 0;
 77 }
 78 /*
 79 
 80 hack数据：
 81 dp不满足，当前最优，不满足最后的答案最优
 82 
 83 6 14
 84 1 2 101
 85 1 3 44
 86 1 4 235
 87 1 6 629
 88 2 3 60
 89 2 4 196
 90 2 5 250
 91 2 6 490
 92 3 4 237
 93 3 5 114
 94 3 6 715
 95 4 5 166
 96 4 6 432
 97 5 6 932
 98 
 99 6 6 
100 1 2 100 
101 2 3 1 
102 2 4 10 
103 3 4 10 
104 3 5 100 
105 4 6 10000
106 
107 */

View Code

2、那么解决上述dp中出现的dp，就需要按深度进行dp，每次枚举下一深度的所有点，子集dp。复杂度$n^33^n$

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cctype>
 6 #include<cmath>
 7 #include<set>
 8 #include<queue>
 9 #include<vector>
10 #include<map>
11 #include<bitset>
12 using namespace std;
13 typedef long long LL;
14 
15 inline int read() {
16     int x = 0, f = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch=='-') f = -1;
17     for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0'; return x * f;
18 }
19 
20 const int N = 100;
21 const LL LLINF = 1e18;
22 const int INF = 1e9;
23 
24 LL dp[(1 << 12) + 10][13], tmp[(1 << 12) + 10], dis[N];
25 int mp[N][N];
26 int n, m;
27 
28 LL solve(int x) {
29     int S = (1 << n) - 1;
30     for (int s = 0; s <= S; ++s)     
31         for (int i = 0; i <= n; ++i) dp[s][i] = LLINF;
32     dp[1 << x][1] = 0;
33     
34     for (int s = 0; s <= S; ++s) {
35         int r = 0;
36         for (int i = 0; i < n; ++i) dis[i] = LLINF;
37         for (int i = 0; i < n; ++i) {
38             if ((s >> i) & 1) 
39                 for (int j = 0; j < n; ++j) 
40                     if (!((s >> j) & 1) && mp[i][j])
41                         r |= (1 << j), dis[j] = min(dis[j], (LL)mp[i][j]);
42         }
43         for (int t = r; t; t = (t - 1) & r) {
44             tmp[t] = 0;
45             for (int i = 0; i < n; ++i) 
46                 if ((t >> i) & 1) tmp[t] += dis[i];
47         }
48         for (int d = 1; d <= n; ++d) {
49             if (dp[s][d] == LLINF) continue;
50             for (int t = r; t; t = (t - 1) & r) 
51                 dp[s | t][d + 1] = min(dp[s | t][d + 1], dp[s][d] + tmp[t] * d);
52         }
53     }
54     LL ans = LLINF;
55     for (int i = 0; i <= n; ++i) ans = min(ans, dp[S][i]);
56     return ans;
57 }
58 
59 int main() {
60 
61     n = read(), m = read();
62     
63     for (int i = 0; i <= n; ++i) 
64         for (int j = 0; j <= n; ++j) mp[i][j] = INF;
65     for (int i = 1; i <= m; ++i) {
66         int u = read() - 1, v = read() - 1, w = read();
67         mp[u][v] = min(mp[u][v], w), mp[v][u] = min(mp[v][u], w);
68     }
69     
70     LL ans = 1e18;
71     for (int i = 0; i < n; ++i) 
72         ans = min(ans, solve(i));
73     cout << ans;
74     
75     return 0;
76 }

View Code

3、随机化算法