[WF2012]infiltration

[WF2012]infiltration

完全图

最多选择logn个点（下取整）（每选择一个点覆盖至少一半的规模）

暴力O(75^5)（不严格）枚举+bitset

（随机化也可过）

#include<bits/stdc++.h>

#define reg register int

#define il inline

#define int long long

#define numb (ch^'0')

using namespace std;

typedef long long ll;

il void rd(ll &x){

    char ch;x=;bool fl=false;

    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

    (fl==true)&&(x=-x);

}

namespace Miracle{

const int N=;

int n;

char con[N][N];

bitset<N>to[N],now;

bool c1(){

    for(reg a1=;a1<=n;++a1)

        if(to[a1].count()==n) return true;

    return false;

}

bool c2(){

    for(reg a1=;a1<=n;++a1)

    for(reg a2=a1+;a2<=n;++a2)

        if((to[a1]|to[a2]).count()==n) return true;

    return false;

}

bool c3(){

    for(reg a1=;a1<=n;++a1)

    for(reg a2=a1+;a2<=n;++a2)

    for(reg a3=a2+;a3<=n;++a3)

        if((to[a1]|to[a2]|to[a3]).count()==n) return true;

    return false;

}

bool c4(){

    for(reg a1=;a1<=n;++a1)

    for(reg a2=a1+;a2<=n;++a2)

    for(reg a3=a2+;a3<=n;++a3)

    for(reg a4=a3+;a4<=n;++a4)

        if((to[a1]|to[a2]|to[a3]|to[a4]).count()==n) return true;

    return false;

}

bool c5(){

    for(reg a1=;a1<=n;++a1)

    for(reg a2=a1+;a2<=n;++a2)

    for(reg a3=a2+;a3<=n;++a3)

    for(reg a4=a3+;a4<=n;++a4)

    for(reg a5=a4+;a5<=n;++a5)

        if((to[a1]|to[a2]|to[a3]|to[a4]|to[a5]).count()==n) return true;

    return false;

}

int main(){

    int o=;

    while(scanf("%d",&n)!=EOF){

        for(reg i=;i<=n;++i) to[i].reset();

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

            scanf("%s",con[i]+);

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

                if(i==j) continue;

                if(con[i][j]=='')to[i][j]=;

                else to[i][j]=;

            }

            to[i][i]=;

        }

        int ans=;

        if(c1()) ans=;

        else if(c2()) ans=;

        else if(c3()) ans=;

        else if(c4()) ans=;

        else if(c5()) ans=;

        else ans=;

        printf("Case %d: %d\n",++o,ans);

    }

    return ;

}

}

signed main(){

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

   Date: 2019/2/26 18:48:55

*/