Steven_MengのBlog

注意到题目实际上是把整个图分成了两个团(团是一个点的集合,其中任意两点之间都有边相连)。

根据我们以前的经验,团什么的都可以随机化搞出来,如P4212 外太空旅行

注意到我们随机化不能写成这个样子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool Check返回能不能构成团
for (register int k=1;k<=10000;++k){
random_shuffle(a+1,a+1+n);
//.........
for (register int i=1;i<=n;++i){
//..........
if (Check(a[1]...a[i])){
if (Check(a[i+1]...a[n])) ans=min(ans,...);
}
else{
break;//后面不能构成团
}
}
}

而是写成:

1
2
3
4
5
6
7
8
9
10
11
12
13
bool Check返回能不能构成团
for (register int k=1;k<=10000;++k){
random_shuffle(a+1,a+1+n);
s={};
//.........
for (register int i=1;i<=n;++i){
//..........
if (Check(s+a[i])){
s.insert(a[i]);
if (Check(a[1]...a[n]除s之外的元素)) ans=min(ans,...);
}
}
}

总的代码,发现只要随机化33次就可以AC。

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
#define MAXN 705
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];
int a[MAXN],stk[MAXN],top,vis[MAXN];
inline int Check(int x){
for (register int i=1;i<=top;++i){
if (G[stk[i]][x]==false){
return false;
}
}
return true;
}
int stk1[MAXN],top1,n,m;
inline int CheckElse(){
top1=0;
for (register int i=1;i<=n;++i){
if (!vis[i]) stk1[++top1]=i;
}
for (register int i=1;i<=top1;++i){
for (register int j=i+1;j<=top1;++j){
if (G[stk1[i]][stk1[j]]==false) return false;
}
}
return true;
}
inline int CalcEdge(int x){
return x*(x-1)/2;
}
inline int Best(){
return CalcEdge(n/2)+CalcEdge(n-n/2);
}
int main(){
n=read(),m=read();
for (register int i=1;i<=m;++i){
int u=read(),v=read();
G[u][v]=G[v][u]=true;
}
for (register int i=1;i<=n;++i){
a[i]=i;
}
int ans=0x7fffffff;
int best=Best();
for (register int t=1;t<=33;++t){
random_shuffle(a+1,a+1+n);
top=0;
memset(vis,0,sizeof(vis));
for (register int j=1;j<=n;++j){
if (Check(a[j])) stk[++top]=a[j],vis[a[j]]=true;
int temp=CalcEdge(top)+CalcEdge(n-top);
if (temp<ans){
if (CheckElse()) ans=temp;
}
}
if (ans==best) break;
}
printf("%d\n",ans==0x7fffffff?-1:ans);
}

数据生成器,$m$设成244550左右就可以使程序WA:

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
#include <bits/stdc++.h>
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<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
vector<pair<int,int> >Edge;
int main(){
int n=700,m=244550;
freopen("data.in","w",stdout);
for (register int i=1;i<=n;++i){
for (register int j=i+1;j<=n;++j){
Edge.push_back(make_pair(i,j));
}
}
random_shuffle(Edge.begin(),Edge.end());
printf("%d %d\n",n,m);
for (register int i=0;i<m;++i){
printf("%d %d\n",Edge[i].first,Edge[i].second);
}
}

 评论