【Codeforces】906C. Party【暴力+BFS位运算优化】

C. Party

【题目描述】

传送门

【题解】

这题的复杂度显然是O(2^nn),当然O(2^nn^2)也可以过。
显然和顺序无关,暴力枚举每个点,这些点必须相互连通,并且覆盖所有点,这样可以用BFS+位运算优化(很好的方法,详情见代码)。

代码如下

#include<cstdio>
using namespace std;
const int MAXN=25,MAXM=(1<<22)+5;
int n,m,hd,tl,vis[MAXN],P[MAXM];
struct QUE{int x,stp;}Ans;
QUE min(QUE x,QUE y){return x.stp<=y.stp?x:y;}
#include<cctype>
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret<<1)+(ret<<3)+ch-48;
    return f?ret:-ret;
}
inline bool check(int x){
    int S=0,y=x;
    while(y) S|=vis[P[y&-y]],y^=(y&-y);
    if(S^((1<<n)-1)) return 0; 
    int vs=0,Q=x&-x;
    while(Q){
        int Now=Q&-Q;
        vs|=Now,Q^=Now,Q|=vis[P[Now]]&x&~vs; 
    }
    return vs==x;
}
void DFS(int x,int Now,int stp){
    if(stp>=Ans.stp) return;
    if(x>n){if(check(Now)) Ans=min(Ans,(QUE){Now,stp});return;}
    DFS(x+1,Now<<1,stp);DFS(x+1,Now<<1|1,stp+1);
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) P[1<<i-1]=i,vis[i]=(1<<i-1);
    for(int i=1,x,y;i<=m;i++) x=read(),y=read(),vis[x]|=(1<<y-1),vis[y]|=(1<<x-1);
    if(m==n*(n-1)/2) return printf("0\n"),0;
    Ans=(QUE){0,(int)1e9};DFS(0,0,0);
    printf("%d\n",Ans.stp);
    for(int i=1;i<=n;i++) if(Ans.x&(1<<i-1)) printf("%d ",i);printf("\n");
    return 0;
}

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部