古往今来的各种传说中存在着很多魔法阵，它们的激活方式也各不相同。传说在北师大电子楼前的小花园里就有一个魔法阵，上次出现还是在很多很多很多年前，但是现在它又出现了！
这时，小Q同学面无表情地说：“传说这个魔法阵都会在都会在来自远古的恶魔Awesome Crystal Monster（ACM）降临的时候出现，现在，这个时候终于要到来了吗！”话音未落，小Q同学已经走到了魔法阵前，取出一个小瓶，开始用瓶中的圣水激活这个魔法阵，“你们快退后，这里就交给我了！”
这个魔法阵由一些点和一些连接这些点的边构成，当小Q同学把圣水滴在一个点上时，和这个点相连的所有边就会被点亮并发出神圣的光芒，当魔法阵所有的边都点亮的时候，就会出现强大的神圣力量。但是小Q同学拥有的圣水非常有限，只有10滴，现在小Q同学想知道他最少可以用多少滴圣水点亮整个魔法阵，如果耗尽圣水也不能点亮，就只能打出一波GG了。第一行包含一个正整数，表示测试数据的组数，
对于每组测试数据，
第一行是两个整数和，表示魔法阵的点数和边数，
接下来行，每行包含两个整数，表示有一条边连接了号点和号点。
对于每组测试数据，如果使用不超过10滴圣水可以点亮整个魔法阵，输出最少需要的圣水滴数，否则输出"GG"（不含引号）。
对于第一组样例，最优方案是在1号点滴一滴圣水，
对于第二组样例，一个最优方案是在1号点和3号点各滴一滴圣水。
思路：
一开始读完题下意识的就觉得是最小点覆盖问题，然而忘记这个图可能会存在（奇数长度）环的问题了，直接闭着眼睛去搞了一发。
然后发现不能处理变成二分图。
当然也不能树型Dp去求最小点覆盖数。
问题焦点肯定锁定在10个点上来。
所以我们着重考虑10个点的问题。
对于这十个点的枚举我想了半天，后来才发现不妨去枚举边。（这题的爆搜思路还是挺隐秘的，反正窝不太常见这种题，我不太能一眼看出来，要思考好久好久啊-----）；
锻炼了这样的能力，蛮开心。
我们要染到所有的边，所以我们不妨去枚举边，对于一条边来讲：
①如果其之前选的点之中选择过了这条边的某个点，那么这条边就已经被染上了不用去管。
②如果这条边没有被染过，那么对应有两种选择，要么去染u，要么去染v.如果就单单这一条边我们就要将两个点都处理了的话是没有必要的，所以我们这里枚举一种情况即可。
那么对于每一条边我们都去枚举情况的话，时间复杂度可是要达到O（2^m）的啊；
看起来是这样的，回归焦点，我们一旦已经枚举过了10个点出来，而当前边还需要选择一个点去选择，那么当前情况就可以剪枝掉。
所以最坏的时间复杂度其实是O（2^10*m）；
那么我们爆搜处理维护最小值即可
Ac代码：
#include<stdio.h> #include<string.h> #include<iostream> using namespace std; struct node { int x,y; }a[2500]; int n,m; int ans; int vis[2500]; void Dfs(int u,int sum) { if(sum>10)return ; if(u==m) { ans=min(ans,sum); return ; } if(vis[a[u].x]==1||vis[a[u].y]==1)Dfs(u+1,sum); else { vis[a[u].x]=1; Dfs(u+1,sum+1); vis[a[u].x]=0; vis[a[u].y]=1; Dfs(u+1,sum+1); vis[a[u].y]=0; } return ; } int main() { int t; scanf("%d",&t); while(t--) { memset(vis,0,sizeof(vis)); scanf("%d%d",&n,&m); for(int i=0;i<m;i++)scanf("%d%d",&a[i].x,&a[i].y); ans=0x3f3f3f3f; Dfs(0,0); if(ans<=10) printf("%d\n",ans); else printf("GG\n"); } }
