题解 P4212 【外太空旅行】
interestingLSY
2018-08-14 12:11:12
这题出的,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;
}
```