CF839E Mother of Dragons 最大团 Bron-Kerbosch算法

标签：bit   static   pow   reg   实现   ++   节点   rac   邻接   

题意简述

给你一个\(n\)个节点的无向图\(G=\{V,E\}\)的邻接矩阵\(g\)和每个点的点权为\(s_i\)，且\(\sum_{i=1}^n s_i = K\)，要你求出\(\mathrm{max} \{ \sum_{u,v \in E} s_u \times s_v\}\)

做法

设两个不相邻的点\(u\)，\(v\)的点权为\(s_u\)和\(s_v\)，令\(a_u = \sum_{g[u][i]=1} s_i, a_v=\sum_{g[v][i]=1} s_i\)，此时这对点\((u,v)\)的贡献为\(a_us_u+a_vs_v\)。

• 不妨设\(a_u\geq a_v\)，若\(s_u=s_u+s_v,s_v=0\)，\(ans\)并不会变小。

所以最优解一定包含选取一个团(完全图)。对于一个\(n\)个点的完全图，这个完全图的答案为\((\frac {K}{n})^2 \times \frac {n(n-1)}{2}\)，所以本题的答案为\((\frac {K}{tot})^2 \times \frac {tot(tot-1)}{2}\)，其中\(tot\)为最大团的大小。

我们采用\(Bron-Kerbosch\)算法来求最大团，采用dfs剪枝的方法，时间复杂度\(O\left( {1.14}^n \right)\)。

当然此题模拟退火也可以过，维护一个序列\({c_n}\)，\(s_i=\frac {c_i}{\sum_j c_j}\)。对于序列进行随机的$\bmod $固定值(如\(100\))意义下的加减，如果更优则转移。

代码实现

#include
using namespace std;
#define re register int
#define ll long long
#define ak *
#define in inline
#define db double
in char getch()
{
    static char buf[1'9') ioi=qwq=='-'?~ioi+1:1,qwq=gc();
    while(qwq>='0'&&qwqans) return ans=nw,true;
    for(re i,v=u+1;vnw&&dfs(v,nw+1)) return true; 
    }
    return false;
}
in int bron_kerbosch()
{
    for(re i=n;i;i--) dfs(i,1),cnt[i]=ans;
    return ans;
}
int main()
{
    n=read();k=read();
    for(re i=1;i

CF839E Mother of Dragons 最大团 Bron-Kerbosch算法

标签：bit   static   pow   reg   实现   ++   节点   rac   邻接   

原文地址：https://www.cnblogs.com/disangan233/p/11143294.html