【图论+状压DP】ABC187 F - Close Group

淩亂°似流年 2024-03-22 18:24 34阅读 0赞

**状压真会不了一点吧**

**还是练的太少了**

**加训加训加训！！！**

[F - Close Group (atcoder.jp)][F - Close Group _atcoder.jp]

题意：

![f2f1874c36004dfdb3b92a64743c6162.png][]

思路：

首先看到N<=18就是状压DP

所以就很自然地考虑0101110这样的点集代表的含义

状态设计：

设dp\[state\]表示这个点集构成的图最少由多少个连通分量组成

为什么这样设计，因为这个就是答案

然后状压DP的转移一般都是去枚举其中一个位，然后构造出一个new\_state，满足一定条件的时候转移

先去把所有 最少由一个连通分量组成 的点集找出来，作为初始化

怎么找呢，就是去考虑转移，当一个点与这个点集的所有点都有边相连的时候，这个新的点集就构成了一个new\_state，此时dp\[new\_state\]=1

dp值为1的点集全部找出来之后，去求一般的点集的dp值

对于一个一般的点集，可以枚举这个点集的子集，答案就是这个子集的dp值和子集的补集的dp值加起来，即由这两个图的最少连通分量相加组成

Code：

#include <bits/stdc++.h>
    
    //#define int long long
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    
    using namespace std;
    
    const int mxn=1e2+10;
    const int mxv=1e6+10;
    const int mod=1e9+7;
    const int Inf=0x3f3f3f3f;
    
    int N,M;
    int u,v;
    int H[mxn],dp[mxv];
    
    void solve(){
        cin>>N>>M;
        for(int i=1;i<=M;i++){
            cin>>u>>v;
            u--,v--;
            H[u]|=(1ll<<v);
            H[v]|=(1ll<<u);
        }
        memset(dp,0x3f,sizeof(dp));
        dp[0]=1;
        for(int x=0;x<(1<<N);x++){
            for(int j=0;j<N;j++){
                if(dp[x]==1&&((H[j]&x)==x)){
                    dp[x|(1<<j)]=1;
                }
            }
        }
        for(int x=1;x<(1<<N);x++){
            for(int y=x;--y&=x;){
                dp[x]=min(dp[x],dp[x^y]+dp[y]);
            }
        }
        cout<<dp[(1<<N)-1]<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[F - Close Group _atcoder.jp]: https://atcoder.jp/contests/abc187/tasks/abc187_f
[f2f1874c36004dfdb3b92a64743c6162.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/d734ed97ed7a440e9bc703856f71630c.png