题目链接

E. Mother of Dragons

分析

这个题的算法实现其实不难，难的是得出其中的结论，题解可以在这里看到
http://codeforces.com/blog/entry/53815

AC code

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define PI acos(-1)
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define INF64 0x3f3f3f3f3f3f3f3f
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define ms(x,v) memset((x),(v),sizeof(x))
#define scint(x) scanf("%d",&x );
#define scf(x) scanf("%lf",&x );
#define eps 1e-10
#define dcmp(x) (fabs(x) < eps? 0:((x) <0?-1:1))
#define ctz(x) ((x)? __builtin_ctzll(x):64)
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef long double DB;
typedef pair<double,double> Pair;
const int maxn = 40;
int ans,n;
ULL g[maxn];
//最大团
void BronKerbosch(ULL clique,ULL allow,ULL forbid){
    if(!allow && !forbid){
        ans = max(ans,__builtin_popcountll(clique));return;
    }
    if(!allow)return;
    int pivot = ctz(allow | forbid);//选择轴点
    ULL choose = allow & ~g[pivot];
    for(int u = ctz(choose) ; u<n ; u += ctz(choose>>(u+1))+1){
        BronKerbosch(clique|(1ULL<<u),allow&g[u],forbid&g[u]);
        allow ^=1ULL<<u;
        forbid|=1ULL<<u;
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int k;
    cin>>n>>k;
    for(int i=0 ; i<n ; ++i){
        g[i] = 0;
        for(int j=0 ; j<n ; ++j){
            ULL x;cin>>x;
            g[i]^=x<<j;
        }
    }
    BronKerbosch(0ULL,(1ULL<<n) - 1,0ULL);
    printf("%.9lf\n",(1.0-1.0/ans)*k*k/2 );
    return 0;
}