BZOJ4080: [Wf2014]Sensor Network 最大团

题解：

就是一个最大团吧。

随机一些贪心插入取最大值。

这个算法效果还是很好的。

正解貌似是一个二分图匹配？不过数学只是有点欠缺还是略过了。

代码：

#include<cstdio>
#include<cctype>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;

#define N 110
int x[N],y[N],p[N];
bool g[N][N];

int ans[N],num,q[N],cnt;
int main(){
#ifndef ONLINE_JUDGE
	freopen("tt.in","r",stdin);
#endif
	int n,d,i,j;
	cin>>n>>d;
	for(i=1;i<=n;++i)
		scanf("%d%d",&x[i],&y[i]);
	for(i=1;i<=n;++i)
		for(j=i+1;j<=n;++j)
			g[i][j]=g[j][i]=((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])<=d*d);
	for(i=1;i<=n;++i)
		p[i]=i;
	int T=1000;
	while(T--){
		for(i=2;i<=n;++i)
			swap(p[i],p[rand()%(i-1)+1]);
		cnt=0;
		for(i=1;i<=n;++i){
			bool ok=1;
			for(j=1;j<=cnt;++j)
				if(!g[p[i]][q[j]]){
					ok=0;
					break;
				}
			if(ok)
				q[++cnt]=p[i];
		}
		if(cnt>num){
			num=cnt;
			memcpy(ans,q,sizeof q);
		}
	}
	printf("%d\n",num);
	for(i=1;i<=num;++i){
		if(i>1)
			putchar(' ');
		printf("%d",ans[i]);
	}
	return 0;
}