6
17
2015
0

bzoj 4080: [Wf2014]Sensor Network

死活过不去的暴力?难道这就是传说中的卡最大团的暴力数据??

上网一看全都是随机化,然后完全不明白

后来想了想什么random_shuffle之后搞一下

然后就过了

对了,次数还可以卡以下所以就把T搞到80才rank3

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <bitset>
#include <deque>
using namespace std;
#define LL long long
#define X first
#define Y second
template<typename T>
inline T sqr(const T &x){ return x*x; }
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
}
const int N = 110;
bitset<N>now,ans,cur,a[N],can;
int order[N],x[N],y[N],d,n;
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
//	srand(2333);
	n=read(); d=read();
	d*=d;
	for (int i=1;i<=n;i++){
		x[i]=read();
		y[i]=read();
		for (int j=1;j<i;j++){
			if (sqr(x[i]-x[j])+sqr(y[i]-y[j])<=d){
				a[i][j]=a[j][i]=1;
			}
		}
	}
	for (int i=1;i<=n;i++) order[i]=i;
	for (int T=1;T<=80;T++){
		for (int i=1;i<=n;i++) can[i]=1,now[i]=0;
		for (int i=1;i<=n;i++){
			if (can[order[i]]){
				can=can&a[order[i]];
				now[order[i]]=1;
			}
		}
		if (now.count()>ans.count()) ans=now;
		random_shuffle(order+1,order+n+1);
	}
	printf("%d\n",(int)ans.count());
	for (int i=1;i<=n;i++){
		if (ans[i]) printf("%d ",i);
	}
	puts("");
	return 0;
}
Category: 未分类 | Tags: bzoj 随机化 乱搞 | Read Count: 352

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com