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次

轉載于:https://www.cnblogs.com/DOlaBMOon/p/7553803.html

總結

以上是生活随笔為你收集整理的CF 839 E-最大团的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。