interestingLSY 的博客

interestingLSY 的博客

题解 P4212 【外太空旅行】

posted on 2018-08-14 12:11:12 | under 题解 |

这题出的,emmmmmmmmmmm..............

首先介绍一类问题:最大团问题

“团”就是指从一个图中选出来一堆点,每对点间都直接有边相连。“最大团”就是指包含的点最多的那个团。这题就是个“最大团问题”

但不幸的是,最大团问题是NPC的。

目前最快的正确解法是状压dp......复杂度为 $O(n^22^n)$ ,这题中 $n=50$ 显然会凉凉

怎么办。。。我们先暴搜一波......

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了!

#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;
}