BZOJ3632: 外太空旅行

Description

大意：求最大团。 

Input

第一行n表示点数，后面若干行每行u，v表示u，v连边

Output

一行，最大团点的数目。 

Sample Input

4
1 2
2 3
3 1
1 4

Sample Output

3

Solution

蒙特卡罗大法好。。另外dfs就：http://blog.csdn.net/popoqqq/article/details/44623165

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define ll int
#define N 51
using namespace std;
ll f[N][N],a[N],vis[N],n,u,v,t,ans;
void work(){
    t=0; memset(vis,0,sizeof vis);
    for (ll i=1;i<=n;i++)
        if (!vis[i]){
            t++;
            for (ll j=i+1;j<=n;j++)
                if (!f[a[i]][a[j]]) vis[j]=1;
        }
    ans=max(ans,t);
}
int main(){
    scanf("%d",&n);
    while (~scanf("%d%d",&u,&v))
        f[u][v]=f[v][u]=1;
    for (ll i=1;i<=n;i++) a[i]=i;
    for (ll i=1;i<=N;i++){
        for (ll j=1;j<=n;j++)
            swap(a[j],a[rand()%n+1]);
        work();
    }
    printf("%d",ans);
}