完全图
最多选择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=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } namespace Miracle{ const int N=80; int n; char con[N][N]; bitset<N>to[N],now; bool c1(){ for(reg a1=1;a1<=n;++a1) if(to[a1].count()==n) return true; return false; } bool c2(){ for(reg a1=1;a1<=n;++a1) for(reg a2=a1+1;a2<=n;++a2) if((to[a1]|to[a2]).count()==n) return true; return false; } bool c3(){ for(reg a1=1;a1<=n;++a1) for(reg a2=a1+1;a2<=n;++a2) for(reg a3=a2+1;a3<=n;++a3) if((to[a1]|to[a2]|to[a3]).count()==n) return true; return false; } bool c4(){ for(reg a1=1;a1<=n;++a1) for(reg a2=a1+1;a2<=n;++a2) for(reg a3=a2+1;a3<=n;++a3) for(reg a4=a3+1;a4<=n;++a4) if((to[a1]|to[a2]|to[a3]|to[a4]).count()==n) return true; return false; } bool c5(){ for(reg a1=1;a1<=n;++a1) for(reg a2=a1+1;a2<=n;++a2) for(reg a3=a2+1;a3<=n;++a3) for(reg a4=a3+1;a4<=n;++a4) for(reg a5=a4+1;a5<=n;++a5) if((to[a1]|to[a2]|to[a3]|to[a4]|to[a5]).count()==n) return true; return false; } int main(){ int o=0; while(scanf("%d",&n)!=EOF){ for(reg i=1;i<=n;++i) to[i].reset(); for(reg i=1;i<=n;++i){ scanf("%s",con[i]+1); for(reg j=1;j<=n;++j){ if(i==j) continue; if(con[i][j]=='1')to[i][j]=1; else to[i][j]=0; } to[i][i]=1; } int ans=0; if(c1()) ans=1; else if(c2()) ans=2; else if(c3()) ans=3; else if(c4()) ans=4; else if(c5()) ans=5; else ans=6; printf("Case %d: %d ",++o,ans); } return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* Date: 2019/2/26 18:48:55 */