uva 818 - Cutting Chains(暴力）

题目链接：uva 818 - Cutting Chains

题目大意：给出一些环以及那些环之间是相连的，问所最少打开即可环，可以将这些环连成一串，注意不是环。

解题思路：因为n最大才15，可以用一个二进制数表示各个环是否被打开，然后判断一下是否还有位置度数大于2，以及是否有环的存在。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; const int N = 20; int n, ans, k, ti, g[N][N]; void init() { ans = n; int a, b; memset(g, 0, sizeof(g)); while (scanf("%d%d", &a, &b) == 2) { if (a == -1 || b == -1) break; g[a-1][b-1] = g[b-1][a-1] = 1; } } int cal(int s) { return s   cal(s/2) + (s&1) : 0; } bool judge() { for (int i = 0; i < n; i++) { if (k & (1<
      
        2) return true; } return false; } bool dfs(int f, int u, int* vis) { if (vis[u]) return true; vis[u] = 1; for (int i = 0; i < n; i++) { if (k & (1<
       
        = ti - 1) { ans = min(ans, cal(k)); } } int main() { int cas = 1; while (scanf("%d", &n) == 1 && n) { init(); for (k = 0; k < (1<