UVA 818 Cutting Chains（状压 + 暴搜）题解

题意：有1~n个小环，他们中的有些互相扣在一起，问你至少切开几个能把这写小环串成一条链

思路：还是太菜了，题目给的n<=15，显然可以暴力解决。

用二进制表示每个环切还是不切，然后搜索所有情况。当一种情况满足一下两点：1.切完之后每一串连在一起的环应该是一条链，没有分支没有环；2.当一个环被切开，那么他就可以当做任意串的连接点，那么显然切开的点+1>=串的数量。

代码：

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<queue>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

typedef long long ll;

using namespace std;

const int maxn =  + ;

const int seed = ;

const ll MOD = ;

const int INF = 0x3f3f3f3f;

int vis[maxn], del[maxn], mp[maxn][maxn];

int n, ans, u, v, ca = , flag;

bool branch(){

    int deg = ;

    for(int i = ; i <= n; i++){

        deg = ;

        if(!del[i]){

            for(int j = ; j <= n; j++){

                if(mp[i][j] && !del[j])

                    deg++;

            }

        }

        if(deg > ) return false;

    }

    return true;

}

bool dfs(int x, int pre){

    bool yes = true;

    vis[x] = ;

    for(int i = ; i <= n; i++){

        if(mp[x][i] && i != pre && !del[i]){

            if(vis[i]) return false;

            yes = dfs(i, x);

            if(!yes) return false;

        }

    }

    return true;

}

bool loop(int &rest){

    memset(vis, , sizeof(vis));

    flag = ;

    for(int i = ; i <= n; i++){

        if(!vis[i] && !del[i]){

            if(!dfs(i, -)) return false;

            rest++;

        }

    }

    return true;

}

int main(){

    while(scanf("%d", &n) && n){

        memset(mp, , sizeof(mp));

        while(scanf("%d%d", &u, &v) && u != - && v != -){

            mp[u][v] = mp[v][u] = ;

        }

        int ans = INF, delet, rest;

        for(int i = ; i < ( << n); i++){

            memset(del, , sizeof(del));

            delet = rest = ;

            for(int j = ; j < n; j++){

                if(i & ( << j)){

                    del[j + ] = ;

                    delet++;

                }

            }

            if(!branch() || !loop(rest)) continue;

            //printf("%d\n", delet);

            if(delet +  >= rest){

                ans = min(ans, delet);

            }

        }

        printf("Set %d: Minimum links to open is %d\n", ca++, ans);

    }

    return ;

}