UVA 818 Cutting Chains(二进制枚举+DFS)

约定不等于承诺〃 2024-02-17 19:05 36阅读 0赞

题意：有n个圆环，其中有一些已经扣在了一起。现在需要打开尽量少的圆环，使得所有圆环可以组成一条链，例如，有5个圆环，1-2,2-3,4-5，则需要打开一个圆环，如圆环4，然后用它穿过圆环3和圆环5后再次闭合4，就可以形成一条链：1-2-3-4-5。  
思路：对任意一个小圆环，可打开可关闭；用二进制表示，0（关）、1（开），n个小圆环就有2^n种情况（即暴力枚举），如（00000,11111其中两种情况（n=5） 全关闭和全打开），所以要判断这些枚举值是否满足条件构成一条单链，就要判断所有圆环是否满足三个条件：  
1、除去打开的圆环之后的所有圆环的分支数必须<=2；  
2、不能存在环；

3、连通分支数-1要<=打开的小圆环数。

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=15+2;
    int vis[maxn],g[maxn][maxn]; 
    int connected;      //连通分支 
    int n;
    bool over_two(int t){    //每个小圆环超过两个分支 
    	for(int i=0;i<n;i++){
    		int cnt=0;
    		for(int j=0;j<n;j++)
    			{
    			if(g[i][j] && !(t&(1<<i)) && !(t&(1<<j)))cnt++;   //圆环 i和j连通并且 i,j都没有被打开 
    			if(cnt>2)return true;      //分支数大于2 
    		}
    	}
    	return false ;
    }
    bool dfs(int x,int last,int t){        //dfs判断是否存在环（圈） 
    	vis[x]=1;
    	for(int i=0;i<n;i++){
    		if(g[x][i]){
    			if(i==last || (t&(1<<i)))continue;//如果是上次访问过的环或者该环已经被打开
    			if(vis[i]) return true;
    			if(dfs(i,x,t))return true;
    		}
    	}
    	return false;
    }
    bool is_ring(int t){
    	memset(vis,0,sizeof(vis));
    	for(int i=0;i<n;i++)
    		if(!vis[i] && !(t&(1<<i))){
    			connected++;        //连通分支个数
    			if(dfs(i,-1,t))return true;
    		}
    		return false;
    }
    int open_ring(int t){     //统计打开的环的个数 
    	int cnt=0;
    	for(int i=0;i<n;i++)
    	if(t&(1<<i))cnt++;
    	return cnt;
    }
    int main(){
    	int kase=0;
    	while(scanf("%d",&n)==1 && n){
    		memset(g,0,sizeof(g));
    		int a,b; 
    		while(scanf("%d%d",&a,&b)==2 && a!=-1 && b!=-1){
    			g[a-1][b-1]=1;
    			g[b-1][a-1]=1;
    		} 
    	    int min1=100000;      
    		for(int i=0;i<(1<<n);i++){
    		connected=0;
    		if(over_two(i) || is_ring(i)) 	 continue;//如果有的分支大于2 或者 存在环
    		int open=open_ring(i);
    		if(connected-1<=open)min1=min(min1,open);
    		}
    
    		printf("Set %d: Minimum links to open is %d\n",++kase,min1);
    	}
    	return 0;
    }