CF 839 E-最大團

CF 839 E

Soltion:

就是怎么求最大團的問題:

以下是\(O(7000\times n^2)\)的做法

求一個最大團,然后將所有的藥水平均分配,到最大團的所有點上,計算答案.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=40;
int n,k;
int G[MAXN+10][MAXN+10];
int lst[MAXN+10];
bool vis[MAXN+10];
inline int doit()
{int res=0;for(int i=1;i<=n;++i)vis[i]=false;for(int i=1;i<=n;++i){bool flag=true;for(int j=1;j<i;++j){if(!vis[j])continue;if(!G[lst[i]][lst[j]]){flag=false;break;}}if(flag){vis[i]=true;++res;}}return res;
}
int main()
{srand(5201314);scanf("%d%d",&n,&k);for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)scanf("%d",&G[i][j]);for(int i=1;i<=n;++i)lst[i]=i;int sz=0;for(int i=1;i<=10000;++i){random_shuffle(lst+1,lst+1+n);sz=max(sz,doit());}printf("%.16lf",(double)k*k/sz*(sz-1)*0.5);return 0;
}

事實上只要rand7000次就夠啦...但我rand了10000次