50186. Hitting set, part II
難度：4.5/5
Second Try: 5/5 Used Time: A lot Used Time: 21:47
沒有辦法一步到位的遞迴...。 考試的時候的思路應該要怎麼想（每一步都要檢查）： 1. 先寫出一個general case的遞迴，能跑出所有組合（並觀察排序方法，你的sample output在組合的哪個位置） 2. 在遞迴的leaf node，要寫出組合是否正確的valider，只要是符合題目（繼續觀察你所有的valid combination） 3. 增加全域變數(min_cnt, min_num之類的)，幫助你紀錄你在遞迴到leaf的時候，要比較、汰換、紀錄什麼資訊。 4. 確認Sample Output都是對的，可以先丟Judge看看有沒有寫錯。 5. 如果丟上去TLE則開始剪枝，最一般的剪枝狀況就是在最上面加上「如果全選的話能不能至少大於target_size」(這題不適用)。這題可以在最上面加上「你選到的set有沒有大於目前我們找到最小的set」。接著比較題目導向的purning就加在選/不選的遞迴式之前，如果不應該選就直接continue或return。（每增加一個新的condition就要test一次）
然後題目就得看好題意...，最好手算過一次Sample Output。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#include <stdio.h>
#include "ta_set.h"
int n;
int k;
ta_Set s[100];
int min_cnt = 100;
ta_Set min_set;
void dfs(ta_Set hit_set, int now_idx, int now_cnt, ta_Set search_set){
#ifdef LARGESTDICTIONARYORDER
if(now_cnt > min_cnt) return;
#endif
#ifdef SMALLESTDICTIONARYORDER
if(now_cnt >= min_cnt) return;
#endif
else if(now_idx == n + 1){
for(int i = 0; i < k; i++) if(!intersect(hit_set, s[i])) return;
min_cnt = now_cnt;
min_set = hit_set;
return;
}
else{
removeElement(&search_set, now_idx);
int can_no_choose = 1;
for(int i = 0; i < k; i++){
if(intersect(search_set, s[i])) continue;
if(!intersect(s[i], hit_set)){
can_no_choose = 0;
break;
}
}
// choose
addElement(&hit_set, now_idx);
dfs(hit_set, now_idx + 1, now_cnt + 1, search_set);
// no choose
if(can_no_choose){
removeElement(&hit_set, now_idx);
dfs(hit_set, now_idx + 1, now_cnt, search_set);
}
addElement(&search_set, now_idx);
}
}
void ipt(){
scanf("%d %d", &n, &k);
for(int i = 0; i < k; i++){
int m, dummy; scanf("%d", &m);
initializeSet(&s[i], n);
while(m--){
scanf("%d", &dummy);
addElement(&s[i], dummy);
}
}
}
int main(){
ipt();
ta_Set hit_set, search_set;
initializeSet(&hit_set, n);
initializeSet(&search_set, n);
for(int i = 1; i <= n; i++) addElement(&search_set, i);
// printf("===\n"); printSet(search_set); printf("===\n");
dfs(hit_set, 1, 0, search_set);
printSet(min_set);
}