题目链接:
https://vjudge.net/problem/UVA-818
题意:
选几个圆环去open。然后该圆环和其他就断开了。然后用这些open的圆环去连接剩下的圆环【最后打开的会合上】，看能不能连成一串。。求最少的open个数。
题解:
n为15.利用位运算去枚举哪几个圆环要open。然后判断剩下圆环有没有与超过2个圆环的连接或者形成环，如果没有，在判断剩下的链个数有没有超过open个数-1.如果条件都符合，那么保留下最小最为答案。
代码:
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 #define MS(a) memset(a,0,sizeof(a)) 5 #define MP make_pair 6 #define PB push_back 7 const int INF = 0x3f3f3f3f; 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 9 inline ll read(){ 10 ll x=0,f=1;char ch=getchar(); 11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 13 return x*f; 14 } 15 ////////////////////////////////////////////////////////////////////////// 16 const int maxn = 1e5+10; 17 18 int n,vis[20],g[20][20],cnt; 19 20 bool two(int s){ 21 for(int i=0; i<n; i++){ 22 if(s & (1<<i)) continue; 23 int cnt = 0; 24 for(int j=0; j<n; j++){ 25 if(s & (1<<j)) continue; 26 if(g[i][j] && i!=j) cnt++; 27 } 28 if(cnt > 2) return true; 29 } 30 31 return false; 32 } 33 34 bool dfs(int s,int now,int fa){ 35 vis[now] = 1; 36 for(int i=0; i<n; i++){ 37 if(!g[now][i] || s&(1<<i) || i==fa) continue; 38 if(vis[i]) return true; 39 if(dfs(s,i,now)) return true; 40 } 41 return false; 42 } 43 44 bool circle(int s){ 45 for(int i=0; i<n; i++){ 46 if(s & (1<<i)) continue; 47 if(vis[i]) continue; 48 cnt++; 49 if(dfs(s,i,-1)) return true; 50 } 51 return false; 52 } 53 54 int cal(int x){ 55 return x==0 ? 0 : cal(x/2)+(x%2); 56 } 57 58 int main(){ 59 int cas = 1; 60 while(scanf("%d",&n) && n){ 61 MS(g); 62 int u,v; 63 while(scanf("%d%d",&u,&v)){ 64 if(u==-1 && v==-1) break; 65 g[u-1][v-1] = g[v-1][u-1] = 1; 66 } 67 int s = (1<<n); 68 int ans = INF; 69 for(int i=0; i<s; i++){ 70 MS(vis); cnt=0; // cnt 表示 如果剩下的环中，没有连成圈的， 那有几条链 71 if(two(i) || circle(i)) continue; 72 if(cal(i) >= cnt-1) // 如果拆下来的环 大于链数-1 才能连成一条链 73 ans = min(ans,cal(i)); 74 } 75 printf("Set %d: Minimum links to open is %d ",cas++,ans); 76 } 77 78 return 0; 79 }