模拟退火
退火大法吼啊！
首先不知道模拟退火的请左转这个题
然后回到我们的这个问题，实际上我们的这个题是图论中的一类经典问题——最大团问题，这个问题是指在一个图中找一个子图是完全图，使这个子图的点数最多。这是一个NP完全问题别说你不知道啥是NP完全，一般情况下解决NP完全问题，模拟退火都有较好的表现。
正片开始：
我们先产生一个排列，然后从前往后的枚举点，考虑这个点是否能加入，能就加入，不能就返回答案，这样我们就得到了一个解，然而它不一定使最优解，这个计算函数长这样：
inline int calc(int *a)
{
for(int i=1;i<=n;++i)
for(int j=1;j<i;++j)
if(!e[a[i]][a[j]]) return n-i+1;
return 0;
}
我们可以每次尝试交换排列中的两个数来退火，就像这样：
void SA()
{
memcpy(a,b,sizeof(b));
for(double t=2048;t>1e-18;t*=delta)
{
int x=rand()%n+1,y=rand()%n+1;
if(x==y) continue;
swap(a[x],a[y]);
int now=calc(a),D=now-ans;
if(D<0) ans=now,memcpy(b,a,sizeof(a));
else if(exp(-D/t)*RAND_MAX<=rand()) swap(a[x],a[y]);
}
}
多次退火到时间上限：
double pre=clock();
while(clock()-pre<0.95*CLOCKS_PER_SEC) SA();
注意记录一下最优解的排列，每次从那里开始。
然后就没有了。
剩下的就只有最有意思的调参了。
代码，在$O2$的加持一般有九十分，洗一下脸说不定就A了
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <ctime>
using namespace std;
const int maxn=55;
const double delta=0.997;
int a[maxn],e[maxn][maxn],n,ans,b[maxn];
inline int calc(int *a)
{
for(int i=1;i<=n;++i)
for(int j=1;j<i;++j)
if(!e[a[i]][a[j]]) return n-i+1;
return 0;
}
void SA()
{
memcpy(a,b,sizeof(b));
for(double t=2048;t>1e-18;t*=delta)
{
int x=rand()%n+1,y=rand()%n+1;
if(x==y) continue;
swap(a[x],a[y]);
int now=calc(a),D=now-ans;
if(D<0) ans=now,memcpy(b,a,sizeof(a));
else if(exp(-D/t)*RAND_MAX<=rand()) swap(a[x],a[y]);
}
}
int main()
{
srand(time(0));
int u,v;
scanf("%d",&n);
if(n==1) {puts("1");return 0;}
while(scanf("%d%d",&u,&v)!=EOF)
e[u][v]=e[v][u]=1;
for(int i=1;i<=n;++i) b[i]=i;
ans=calc(b);
double pre=clock();
while(clock()-pre<0.95*CLOCKS_PER_SEC) SA();
printf("%d\n",n-ans);
return 0,QAQ;
}