BZOJ3632: 外太空旅行

BZOJ3632: 外太空旅行

https://lydsy.com/JudgeOnline/problem.php?id=3632

分析:

• 最大团问题，通常使用随机化算法解决这种数据范围的题目。
• 即每次随一个排列，优先插靠前的点。
• 这个的正确率还是挺高的。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
#define N 55
int G[N][N],n,ans,id[N],vis[N],visc;
int calc() {
    int i,j,re=0;
    visc++;
    for(i=1;i<=n;i++) {
        if(vis[i]!=visc) {
            re++;
            for(j=i+1;j<=n;j++) if(!G[id[i]][id[j]]) {
                vis[j]=visc;
            }
        }
    }return re;
}
int main() {
    srand(20020514); rand();
    scanf("%d",&n);
    int x,y,i;
    while(scanf("%d%d",&x,&y)!=EOF) G[x][y]=G[y][x]=1;
    for(i=1;i<=n;i++) id[i]=i;
    random_shuffle(id+1,id+n+1);
    for(x=1;x<=1000;x++) {
        for(i=1;i<=n;i++) swap(id[i],id[rand()%i+1]);
        ans=max(ans,calc());
    }
    printf("%d\n",ans);
}

BZOJ3632: 外太空旅行

原文：https://www.cnblogs.com/suika/p/10264159.html