题意：有n个boss,m种武器，每种武器选用的时候需要有一定的花费ci,然后这个武器可以消灭掉其中一些BOSS，问你消灭完所有的BOSS，需要的最少花费是多少。
当时比赛的时候，看到这题以为是什么网络流的题，一种熟悉的感觉，后来才发现，购买一次武器可以消灭掉那么多怪物才不是什么费用流呢。赛后得知这个叫重复覆盖，然后只能用搜的办法，其中搜的比较机智的办法就是用DLX，然后前两天认真的学习了一下DLX，昨天看着别人的代码A了一道题练手。
今天做的时候首先就是将昨天的东西模板化了一下。DLX首先需要初始化，所以有init的函数，然后link,remove,resume就抄昨天的就好了。
今天覆盖的题目不一样就在于它是带权的，其实平时做的也是带权的，权值就是等于深度，这题的权值就不一定等于深度了,所以搜索的时候带个费用就好（其实可以直接将dep改成费用的）。然后搜到比当前最优解不优的情况就return，对于100的数据量就应该不会超时了。跑出来400多ms。
|
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 |
#pragma warning(disable:4996)#include<iostream>#include<string>#include<cstring>#include<cstdio>#include<cmath>#include<vector>using
namespace std;#define maxnode 15000 // 最多的结点数#define maxn 150 // 最多的行列数struct
DLX{ int
L[maxnode], R[maxnode], U[maxnode], D[maxnode]; int
row[maxnode], col[maxnode]; int
S[maxn], H[maxn]; int
size; int
n; int
cost[maxn]; int
best; void
init(int
tot) { n = tot; for
(int i = 0; i <= n; i++){ S[i] = 0; U[i] = D[i] = i; L[i + 1] = i; R[i] = i+1; }R[n] = 0; memset(H, -1, sizeof(H)); size = n + 1; best = 1000000000; } void
link(int
r, int
c) { S[c]++; row[size] = r; col[size] = c; U[size] = U[c]; D[U[c]] = size; D[size] = c; U[c] = size; if
(H[r] == -1) H[r] = L[size] = R[size] = size; else{ L[size] = L[H[r]]; R[L[H[r]]] = size; R[size] = H[r]; L[H[r]] = size; } size++; } void
remove(int
c) { for
(int i = D[c]; i != c; i = D[i]){ L[R[i]] = L[i]; R[L[i]] = R[i]; } } void
resume(int
c) { for
(int i = U[c]; i != c; i = U[i]){ L[R[i]] = R[L[i]] = i; } } void
dance(int
dep,int
curc) { if
(curc> best) return; if
(R[0] == 0){ if
(curc < best) best = curc; return; } int
minv = maxn; int
c; for
(int i = R[0]; i; i = R[i]){ if
(S[i] < minv) minv = S[i], c = i; } for
(int i = D[c]; i != c; i = D[i]){ remove(i); for
(int j = R[i]; j != i; j = R[j]){ remove(j); } dance(dep + 1,curc+cost[row[i]]); for
(int j = L[i]; j != i; j = L[j]){ resume(j); } resume(i); } return; }}dlx;int
n, m;int
vis[maxn];int
main(){ while
(cin >> n >> m) { memset(vis, 0, sizeof(vis)); dlx.init(n); int
ci, ki; int
tcost = 0; for
(int i = 1; i <= m; i++){ scanf("%d%d", &ci, &ki); tcost += ci; dlx.cost[i] = ci; int
ti; for
(int j = 1; j <= ki; j++){ scanf("%d", &ti); vis[ti] = true; dlx.link(i, ti); } } bool
flag = true; for
(int i = 1; i <= n; i++){ if
(!vis[i]) { flag = false; break; } } if
(!flag) { puts("-1"); continue; } dlx.best = tcost; dlx.dance(0, 0); printf("%d\n", dlx.best); } return
0;} |
FZU2165 v11(带权的重复覆盖),布布扣,bubuko.com
原文：http://www.cnblogs.com/chanme/p/3669576.html