Steven_MengのBlog

传送门
题意:求最大团,团是一个点的集合,其中任意两点都有边相连。
最大团属于$NPC$问题None Player Characters
虽然数据范围小,$n \le 50$,但是直接暴搜肯定超时。
考虑随机化,每次打乱点的总集合$S$
从$S$中取出点$v$,若$v$与$Ans$中的所有点都有边相连,则将$v$加入$Ans$,否则跳过$v$

实践证明随机化个$1000$次就能$AC$

正确性显(bu)然(hui)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define MAXN 55
using namespace std;
inline int read() {
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9') {
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9') {
x=(x*10)+(ch-'0');
ch=getchar();
}
return x*f;
}
int G[MAXN][MAXN];
void AddEdge(int u,int v){
G[u][v]=true;
G[v][u]=true;
}
int a[MAXN];
int stk[MAXN],top;
int main(){
int n=read(),u,v;
int maxn=0;
while (scanf("%d%d",&u,&v)!=EOF&&u!=0&&v!=0){
AddEdge(u,v);
maxn=max(maxn,u),maxn=max(maxn,v);
}
for (register int i=1;i<=n;++i){
a[i]=i;
}
int ans=-0x7fffffff;
srand(time(NULL));
for (register int k=0;k<10000;++k){
random_shuffle(a+1,a+1+n);
top=0;
stk[++top]=a[1];
for (register int i=2;i<=n;++i){//找出v
bool flag=true;
for (register int j=1;j<=top;++j){//判断是否有边相连
if (!G[stk[j]][a[i]]){
flag=false;
break;
}
}
if (flag==true){
stk[++top]=a[i];//加入集合Ans
}
}
ans=max(ans,top);
}
printf("%d\n",ans);
}

 评论