bzoj 4080: [Wf2014]Sensor Network【瞎搞+随机化】

参考：https://blog.csdn.net/YihAN_Z/article/details/73380387

一点都不想写正解.jpg

random_shuffle一下然后贪心的加点，和ans取max即可。biutset非常方便

正解好像是最大团还是二分图最大独立集来着？

#include<iostream>

#include<cstdio>

#include<bitset>

#include<algorithm>

using namespace std;

const int N=105;

int n,d,q[N];

bitset<N>a[N],now,ans,v,b;

struct qwe

{

	int x,y;

	bool operator < (const qwe& a) const

	{

		return x<a.x;

	}

	int operator | (const qwe& a) const

	{

		return (x-a.x)*(x-a.x)+(y-a.y)*(y-a.y);

	}

}p[N];

int main()

{

	scanf("%d%d",&n,&d);

	for(int i=1;i<=n;i++)

	{

		scanf("%d%d",&p[i].x,&p[i].y);

		q[i]=i,v[i]=1;

	}

	for(int i=1;i<=n;i++)

		for(int j=i+1;j<=n;j++)

			if((p[i]|p[j])<=d*d)

				a[i][j]=a[j][i]=1;

	for(int i=1;i<=1000;i++,random_shuffle(q+1,q+n+1))

	{

		b=v;

		now.reset();

		for(int j=1;j<=n;j++)

			if(b[q[j]])

				now[q[j]]=1,b&=a[q[j]];

		if(now.count()>ans.count())

			ans=now;

	}

	printf("%d\n",ans.count());

	for(int i=1;i<=n;i++)

		if(ans[i])

			printf("%d ",i);

	return 0;

}

巴特西

bzoj 4080: [Wf2014]Sensor Network【瞎搞+随机化】

最新文章

热门文章