【习题 7-4 UVA-818】Cutting Chains

在这里输入题意

【题解】

二进制枚举要解开哪些环。

把所有和它相关的边都删掉。

对于剩下的联通分量。

看看是不是每一个联通分量都是一条链

    ->每个点的度数都不大于2

    ->不是环。

同时剩余的联通分量的个数x

解开的环的个数y

y>=x-1才行

满足以上条件即可

【代码】

#include <bits/stdc++.h>

using namespace std;

const int N = 20;

int n;

int g[N][N];

bool vis[N];

bool dfs(int x,int pre){

    vis[x]=1;

    int count = 0;

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

        if (g[x][i]>0 && i!=pre && !vis[i]){

            count++;

            if (count>2) return false;

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

        }else {

            if (i==pre) count++;

            if (count>2) return false;

            if (g[x][i]>0 && i!=pre && vis[i]) return false;

        }

    return true;

}

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

	ios::sync_with_stdio(0),cin.tie(0);

	int kase = 0;

    while (cin >>n && n){

        memset(g,255,sizeof g);

        int x,y;

        while (cin >> x >> y && !(x==-1 && y==-1)){

            g[x][y] = 1;g[y][x] = 1;

        }

        int ma = 1<<n;

        int ans = n;

        for (int i = 0;i < ma;i++){

            int out = 0;

            memset(vis,0,sizeof vis);

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

                if ((1<<j)&i){

                    out++;

                    vis[j+1] = 1;

                    for (int k = 1;k <= n;k++)

                        if (g[j+1][k]==1)

                            g[j+1][k] = g[k][j+1] = 0;

                }

            }

            int lian = 0;

            bool ok = true;

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

                if (!vis[i]){

                    ok = ok&dfs(i,-1);

                    if (!ok) break;

                    lian++;

                }

            if (ok && lian-1<=out){

                ans = min(ans,out);

            }

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

                if ((1<<j)&i)

                    for (int k = 1;k <= n;k++)

                        if (g[j+1][k]==0)

                            g[j+1][k] = g[k][j+1] = 1;

        }

        cout << "Set "<<++kase<<": Minimum links to open is "<<ans << endl;

    }

	return 0;

}

巴特西

【习题 7-4 UVA-818】Cutting Chains

最新文章

热门文章