题解 P4212 【外太空旅行】

interestingLSY

2018-08-14 12:11:12

Solution

这题出的,emmmmmmmmmmm.............. 首先介绍一类问题:**最大团问题** “团”就是指从一个图中选出来一堆点,每对点间都**直接**有边相连。“最大团”就是指包含的点最多的那个团。这题就是个“最大团问题” 但不幸的是,最大团问题是**NPC**的。 目前最快的**正确解法**是状压dp......复杂度为$O(n^22^n)$,这题中 $n=50$ 显然会凉凉 怎么办。。。我们先暴搜一波...... ```cpp int n; bool gay[MAXN][MAXN]; int gaycnt[MAXN]; bool sel[MAXN]; il bool Cansel( int pos , int upp , int selcnt ){ if( gaycnt[pos] < selcnt ) return 0; For(i,upp) if(sel[i]&&!gay[i][pos]) return 0; return 1; } int ans = 0; void Dfs( int pos , int tans , int cnt ){ if( pos == n+1 ){ Mymax(ans,tans); return; } if( tans + n-pos+1 <= ans ) return; int pmax = tans; Forx(i,pos,n) pmax += (int)Cansel(i,pos-1,cnt); if( pmax <= ans ) return; sel[pos] = 0; Dfs(pos+1,tans,cnt); if( Cansel(pos,pos-1,cnt) ){ sel[pos] = 1; Dfs(pos+1,tans+1,cnt+1); sel[pos] = 0; } } ``` 好。70分。(楼下dalao各种剪枝90分%%%%%%) 然后。。点开分类标签,"乱搞"?emmmmmmmmm........ 打不了表,考虑随机。 随机生成一个数列,并从前往后选。 WTF?AC了! ```cpp #define MAXN 60 int n; bool gay[MAXN][MAXN]; int gaycnt[MAXN]; int u[MAXN]; int s[MAXN], top; int ans = 0; bool Check( int pos ){ int v = ::u[pos]; if( gaycnt[v] < top ) return 0; For(i,top){ if(!gay[s[i]][v]) return 0; } return 1; } int main(){ Ms(gay); scanf("%d",&n); int a,b; while( scanf("%d%d",&a,&b) != EOF ){ gay[a][b] = gay[b][a] = 1; gaycnt[a]++; gaycnt[b]++; } For(i,n) u[i] = i; srand((ull)new char); For(i,100000){ top = 0; random_shuffle(u+1,u+1+n); int tans = 0; For(i,n){ if(Check(i)){ s[++top] = u[i]; tans++; } } Mymax(ans,tans); if( ans == n ) break; } printf("%d\n",ans); return 0; } ```