题目链接：【topcoder】SRM696 div1 550 Clicounting
首先， 最大团是O(n⋅2n)求解的，就是我们dfs枚举每个点选与不选，选的话就判断是否和之前选的点有边，所有点枚举完选不选后就更新一次最大团。
考虑到如果n比较小，我们可以将边集二进制压缩，那么判断是否和之前选的点有边，只要看当前的点的边集是否完全包含之前的点即可。这时候最大团复杂度可以为O(2n)。
现在我们考虑dp1[state]表示选点的集合二进制为state（1表示选，0表示不选）下的最大团大小，然后我们可以对dp1做高维前缀最大值，即可得到dp1[state]表示选点的集合二进制为state的子集下的最大团大小。
然后本题一共38个点，10条不确定边，我们可以考虑将不确定边所连的点丢入A集合，其余点丢入B集合，如果A集合的点数少于一半，可以再从B集合随便选一些点丢入A集合，使得两边点数都不会超过20，这样我们就可以进行折半枚举了。
考虑对B集合的点求出dp1，然后我们枚举A集合的选点情况，然后记录每种选点方案下所用未知边的状态，记为used（used为二进制状态，1表示用未知边，0表示不用），同时记录可以选的B集合的点为state（该选点方案所选的每个点都和state内为1的点有边）。然后我们可以更新答案dp2[used]=max(dp2[used],cnt+dp1[state])。
最后我们只要再对dp2做一遍高维最大值，即可得到每种选边方案下的最大团大小了。
#include <bits/stdc++.h>
using namespace std ;
#define clr( a , x ) memset ( a , x , sizeof a )
const int MAXN = 50 ;
typedef long long LL ;
vector < string > s ;
int G[MAXN][MAXN] ;
int n , m , p ;
int dp1[1 << 20] ;
int dp2[1 << 10] ;
int edge[MAXN] ;
int spc[MAXN] ;
int idx[MAXN] ;
int sta[MAXN] ;
void dfs1 ( int cur , int state , int cnt ) {
if ( cur == p ) dp1[state] = cnt ;
else {
dfs1 ( cur + 1 , state , cnt ) ;
if ( ( state & edge[cur] ) != state ) return ;
dfs1 ( cur + 1 , state | 1 << cur , cnt + 1 ) ;
}
}
void dfs2 ( int cur , int state , int cnt , int used ) {
if ( cur == n ) dp2[used] = max ( dp2[used] , cnt + dp1[state] ) ;
else {
dfs2 ( cur + 1 , state , cnt , used ) ;
for ( int i = 0 ; i < cnt ; ++ i ) {
if ( !~G[idx[cur]][sta[i]] ) return ;
used |= G[idx[cur]][sta[i]] ;
}
sta[cnt] = idx[cur] ;
dfs2 ( cur + 1 , state & edge[cur] , cnt + 1 , used ) ;
}
}
int cmp ( const int& a , const int& b ) {
return spc[a] < spc[b] ;
}
class Clicounting {
public :
int count ( vector < string > g ) {
n = g.size () ;
clr ( G , -1 ) ;
clr ( spc , 0 ) ;
clr ( dp1 , 0 ) ;
clr ( dp2 , 0 ) ;
clr ( edge , 0 ) ;
for ( int i = m = 0 ; i < n ; ++ i ) {
idx[i] = i ;
for ( int j = 0 ; j < n ; ++ j ) {
if ( g[i][j] == '0' ) G[i][j] = -1 ;
else if ( g[i][j] == '1' ) G[i][j] = 0 ;
else if ( g[i][j] == '?' && i < j ) {
G[i][j] = G[j][i] = 1 << ( m ++ ) ;
spc[i] = spc[j] = 1 ;
}
}
}
sort ( idx , idx + n , cmp ) ;
for ( p = 0 ; !spc[idx[p]] && p <= n / 2 ; ++ p ) ;
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j = 0 ; j < p ; ++ j ) {
if ( ~G[idx[i]][idx[j]] ) edge[i] |= 1 << j ;
}
}
dfs1 ( 0 , 0 , 0 ) ;
int n1 = 1 << p , n2 = 1 << m ;
for ( int i = 1 ; i < n1 ; i <<= 1 ) {
for ( int j = 0 ; j < n1 ; ++ j ) {
if ( j & i ) continue ;
dp1[j ^ i] = max ( dp1[j ^ i] , dp1[j] ) ;
}
}
dfs2 ( p , n1 - 1 , 0 , 0 ) ;
for ( int i = 1 ; i < n2 ; i <<= 1 ) {
for ( int j = 0 ; j < n2 ; ++ j ) {
if ( j & i ) continue ;
dp2[j ^ i] = max ( dp2[j ^ i] , dp2[j] ) ;
}
}
int ans = 0 ;
for ( int i = 0 ; i < n2 ; ++ i ) {
ans += dp2[i] ;
}
return ans ;
}
} ;
int main () {
while ( ~scanf ( "%d" , &n ) ) {
Clicounting* it = new Clicounting ;
s.clear () ;
for ( int i = 0 ; i < n ; ++ i ) {
s.push_back ( "" ) ;
cin >> s[i] ;
}
printf ( "%d\n" , it->count ( s ) ) ;
}
return 0 ;
}
