【题意】：你是一个猎人，这里有n(n <= 21)棵树和一只猴子，你想猎杀这只猴子，但你不知道这只猴子具体在哪棵树上。每一次你可以随便射击一棵树，如果猴子在这课树上就会被杀掉。如果猴子不在这棵树上，他一定会跳到与当前所处的树相邻的其他树。给出树与树之间的相邻关系，问猎杀这只猴子的最少开枪数是多少，并输出射击的方案，如果存在多组相等开枪数的方案则输出字典序最小的那一组。
【题解】：非常好的搜索题！刚开始以为是个博弈的东西，后来一直推不到最优决策，意识到数据有这么少，应该可以搜索过去。
因为n小于等于21，可以采用状态压缩。对于猴子可能在的某些棵树标记为1，否则标记为0，最终状态为全0，即0.
猴子从当前的树跳到相邻的树这个要先预处理，以后每次可以用O(n)的时间复杂度转移状态。
不可能存在猴子的树是不用管的，这里可以剪枝；如果m > n - 1即关系中存在环则一定无解。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "queue"
5 #include "string"
6 using namespace std;
7 int n, m;
8 bool visit[1<<22];
9 int edge[22];
10 string ans;
11 struct Node {
12 int mask;
13 string path;
14 Node(){}
15 Node(int _mask, string _path) {
16 mask = _mask, path = _path;
17 }
18 };
19
20 bool bfs() {
21 queue<Node> que;
22 memset(visit, false, sizeof(visit));
23 que.push(Node((1 << n) - 1, ""));
24 visit[(1<<n)-1] = true;
25 while(!que.empty()) {
26 Node now = que.front();
27 que.pop();
28 for(int i = 0; i < n; i++) {
29 if(now.mask & (1 << i)) {
30 int mask = now.mask ^ (1 << i);
31 int newmask = 0;
32 for(int j = 0; j < n; j++)
33 if(mask & (1 << j)) newmask |= edge[j];
34 if(visit[newmask]) continue;
35 visit[newmask] = true;
36 char ch = i + '0';
37 string tmp = now.path + ch;
38 if(newmask == 0) {
39 ans = tmp;
40 return true;
41 }
42 que.push(Node(newmask, tmp));
43 }
44 }
45 }
46 return false;
47 }
48
49 void solve() {
50 if((m > n - 1) || !bfs()) printf("Impossible\n");
51 else {
52 printf("%d:", ans.length());
53 for(int i = 0; i < ans.length(); i++) printf(" %d", ans[i] - '0');
54 printf("\n");
55 }
56 return;
57 }
58
59 int main() {
60 while(~scanf("%d%d", &n, &m)) {
61 if(!n && !m) break;
62 memset(edge, 0, sizeof(edge));
63 for(int i = 0; i < m; i++) {
64 int u, v;
65 scanf("%d%d", &u, &v);
66 edge[u] |= (1 << v), edge[v] |= (1 << u);
67 }
68 solve();
69 }
70 return 0;
71 }