Codeforces 839E Mother of Dragons（极大团）

【题目链接】 http://codeforces.com/contest/839/problem/E

【题目大意】

　　现在有一些点，现在你有k的液体，随意分配给这些点，
　　当两个点有边相连的时候，他们能产生分配的液体乘积之和的价值，问最大价值

【题解】

　　考虑相同液体分给两个相连的点的时候，根据不等式x+y<=2sqrt(xy)的取等条件，
　　一定是平均分的时候价值最大，考虑多个相连，完全图的时候产生价值更大，
　　因此答案一定是一个极大团，记团大小为ans，Ans=ans*(ans-1)/2*sqr(k/ans)
　　答案取决于(ans-1)/ans的大小，根据盐水加盐性质，答案正比于ans的大小，
　　所以求最大的极大团，也就是最大团用来计算答案是最优的。

【代码】

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

namespace BronKerbosch{

    const int N=200;

    int G[N][N],Allow[N][N],Forbid[N][N],Num[N][N],Ans;

    void Initialize(int n){

        Ans=0;

        for(int i=1;i<=n;i++)Allow[1][i]=i;

        memset(G,0,sizeof(G));

    }

    void Add_Edge(int x,int y){G[x][y]=G[y][x]=1;}

    void Dfs(int x,int Nn,int An,int Fn){

        if(!An&&!Fn){Ans=max(Ans,Nn);return;}

        if(!An)return;

        int key=Allow[x][1];

        for(int j=1;j<=An;j++){

            int v=Allow[x][j],tAn=0,tFn=0;

            if(G[key][v])continue;

            for(int i=1;i<=Nn;i++)Num[x+1][i]=Num[x][1]; Num[x+1][Nn+1]=v;

            for(int i=1;i<=An;i++)if(G[v][Allow[x][i]])Allow[x+1][++tAn]=Allow[x][i];

            for(int i=1;i<=Fn;i++)if(G[v][Forbid[x][i]])Forbid[x+1][++tFn]=Forbid[x][i];

            Dfs(x+1,Nn+1,tAn,tFn);

            Allow[x][j]=0; Forbid[x][++Fn]=v;

        }

    }

}

int n,K,x,y;

int main(){

    while(~scanf("%d%d",&n,&K)){

        using namespace BronKerbosch;

        Initialize(n);

        for(int i=1;i<=n;i++){

            for(int j=1;j<=n;j++){

                scanf("%d",&x);

                if(x&&i!=j)Add_Edge(i,j);

            }

        }Dfs(1,0,n,0);

        double res=0;

        if(Ans>1)res=1.0*(Ans-1)/2.0/Ans;

        printf("%.10f\n",res*K*K);

    }return 0;

}