Steven_Meng's Blog

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

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

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

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;//后面不能构成团
		}
	}
}

而是写成：

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。

#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：

#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);
	}
}