传送门
题意：求最大团，团是一个点的集合，其中任意两点都有边相连。
最大团属于NPC问题None Player Characters
虽然数据范围小，n≤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
|
#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){
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=max(ans,top);
}
printf("%d\n",ans);
}
|
