BZOJ3632:外太空旅行 随机化算法

思路:

直接随机出很多排列,然后按照顺序贪心加入当前的团,然后每一次更新答案.

不过这为什么是对的呢?

...

...

...

...

...

...

这个问题比较高深,等我变厉害了再来解释解释.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
int G[51][51],seq[51],in[51];
int main(){
    int n;scanf("%d",&n);
    int a,b;while(scanf("%d%d",&a,&b)==2)G[a][b]=G[b][a]=1;
    register int i,j;
    for(i=1;i<=n;++i)seq[i]=i;
    int res=0;
    for(int T=1;T<=5000;++T){
        for(i=1;i<=n;++i)swap(seq[i],seq[rand()%i+1]);
        int nowans=0;memset(in,0,sizeof in);
        for(i=1;i<=n;++i){
            bool ok=1;
            for(j=1;j<i;++j)if(in[seq[j]]&&!G[seq[i]][seq[j]]){ok=0;break;}
            if(ok)in[seq[i]]=1,++nowans;
        }
        res=max(res,nowans);
    }
    printf("%d",res);
    return 0;
}