题目大意：给出n个环（类似奥运五环的那种环），要求你打开其中的m个环，然后以这m个环为中介，使得所有的环能形成一条链
解题思路：暴力枚举，用二进制表示断开的环的位置和数量。 断开环后，和该环相连都断开了，也就是该环变成了一个孤立的环 接着判断一下非断开的环能否连成一个环，，如果能连成一个环，那就不可能通过m个环当中介连成一条链 还得判断一下非断开的环的度，如果度超过2，也不能变成一条链
;#define maxn 20int g[maxn][maxn], m[maxn][maxn], vis[maxn], n, ans;int bitcount(int s) {return s ? s % 2 + bitcount(s / 2): 0;}void dfs(int cur, int f) {for(int i = 0; i < n; i++)if(i != f && m[cur][i]) {vis[i]++;if(vis[i] < 2)dfs(i,cur);}}bool judge(int S) {int d[maxn], broke = 0, link = 0;for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)m[i][j] = g[i][j];memset(vis,0,sizeof(vis));memset(d,0,sizeof(d));//把和broke的珠子相连的线段去掉for(int i = 0; i < n; i++)if((1 << i) & S) {broke++;for(int j = 0; j < n; j++)m[i][j] = m[j][i] = 0;}//纪录一下不是broke的珠子的度数for(int i = 0; i < n; i++)if(!((1 << i) & S)) {for(int j = 0; j < n; j++)if(m[i][j])d[i]++;if(d[i] > 2)return false;}//处理各个串是否会形成环和一共有几个串for(int i = 0; i < n; i++)if(!vis[i] && !((1 << i) & S)) {link++;vis[i]++;dfs(i,-1);}for(int i = 0; i < n; i++)if(vis[i] >= 2)return false;if(link – 1 > broke)return false;return true;}void solve() {ans = 50;int End = (1 << n);for(int i = 0; i < End; i++)if(judge(i))ans = min(ans, bitcount(i));}int main() {int cas = 1;while(scanf(“%d”, &n) == 1 && n) {int x, y;memset(g,0,sizeof(g));while(scanf(“%d%d”, &x, &y)) {if(x == -1 && y == -1)break;g[x – 1][y – 1] = g[y – 1][x – 1] = 1;}solve();printf(“Set %d: Minimum links to open is %d\n”, cas++, ans);}return 0;}
人，也总是很难发现自己的错误，
