UVA-818 Cutting Chains （位压缩+暴力搜索）

题目大意：一种环能打开和闭合。现在有n(1<=n<=15)个编号为1~n的环错综复杂的连接着，要打开一些环重新连接使这n个环能构成一条链，问最少需要打开几次环可达到目的？

题目分析：用二进制数表示要打开的环的集合，总共2^n种情形，枚举每一种情况。当把将要打开的环打开后，此环是孤立的，接下来就要判断剩下的环还与几个环连着，如果有的环仍然与两个以上的环连着则该方案不可行，不可能构成链；然后判断剩下的环有没有连成一个圈，如果有，则该方案不可行；最后，判断完前两个条件之后，所有的环都一定处于某条短链（长度小于等于n）中，只需判断一下短链的条数是否小于等于打开的环数加1，若不成立，则一定连不成一条链，若成立，则该方案可行。

代码如下：

# include<iostream>

# include<cstdio>

# include<set>

# include<cstring>

# include<algorithm>

using namespace std;

int n,ans,st[15],s[15],vis[15];

int bitCount(int sta)

{

    return sta==0?0:bitCount(sta>>1)+(sta&1);

}

void dfs(int u,int pre)

{

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

        if(i!=pre&&s[u]&(1<<i)){

            ++vis[i];

            if(vis[i]<2)

                dfs(i,u);

        }

    }

}

bool ok(int sta)

{

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

        s[i]=st[i];

    ///打开环

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

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

            s[i]=0;

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

                if(j!=i&&s[j]&(1<<i))

                    s[j]^=(1<<i);

            }

        }

    }

    ///判度

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

        if(!(sta&(1<<i))&&bitCount(s[i])>2)

            return false;

    ///判圈

    int link=0;

    memset(vis,0,sizeof(vis));

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

        if(!vis[i]&&!(sta&(1<<i))){

            ++link;

            ++vis[i];

            dfs(i,-1);

        }

    }

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

        if(vis[i]>=2)

            return false;

    ///判链

    if(link-1>bitCount(sta))

        return false;

    return true;

}

int main()

{

    int a,b,cas=0;

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

    {

        memset(st,0,sizeof(st));

        while(scanf("%d%d",&a,&b))

        {

            if(a==-1&&b==-1)

                break;

            st[a-1]|=(1<<(b-1));

            st[b-1]|=(1<<(a-1));

        }

        ans=n;

        int tot=1<<n;

        for(int i=0;i<tot;++i)

            if(ok(i))

                ans=min(ans,bitCount(i));

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

    }

    return 0;

}

巴特西

UVA-818 Cutting Chains （位压缩+暴力搜索）

最新文章

热门文章