记录编号	192436	评测结果	AAAAAAAAAA
题目名称	[NOI 2003]智破连环阵	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2015-10-10 22:04:02	内存使用	1.64 MiB

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<deque>
#include<cstring>
using namespace std;
const int SIZEN=110,maxn=0x7fffffff/2;
int N,M,R,ma=maxn;
int nowans[SIZEN];
deque<int> s[SIZEN];
bool C[SIZEN][SIZEN][SIZEN]={0};
int use[SIZEN]={0};//用多少炸弹可以把i~m炸毁
int maxl[SIZEN]={0};
int D[SIZEN][SIZEN]={0};
int f[SIZEN],co[SIZEN];
int ans[SIZEN]={0};
class miku
{
public:
	int x,y;
}Bomb[SIZEN],w[SIZEN];
void read()
{
	scanf("%d%d%d",&M,&N,&R);ma=N;
	for(int i=1;i<=M;i++) scanf("%d%d",&w[i].x,&w[i].y);
	for(int i=1;i<=N;i++) scanf("%d%d",&Bomb[i].x,&Bomb[i].y);
}
int Dist(miku a,miku b){	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
bool find(int x)
{
	for(int i=0;i<s[x].size();i++)
	{
		int w=s[x][i];
		if(!co[w])
		{
			co[w]=1;
			if(!f[w]||find(f[w]))
			{
				f[w]=x;
				nowans[x]=w;
				return 1;
			}
		}
	}
	return 0;
}
void addseg(int fr,int to,int p)
{
	for(int i=1;i<=N;i++) 
		if(C[fr][to][i]) s[p].push_back(i);
}
void dfs(int x,int len)//当前划分到了哪和当前划分了几块
{
	if(len+use[x]>=ma+1) return;
	if(x>M) 
	{
		ma=len-1;
		//cout<<ma<<endl;
		for(int i=0;i<=ma;i++) ans[i]=nowans[i];
		return;
	}
	for(int i=maxl[x];i>=x;i--)
	{
		s[len].clear();
		addseg(x,i,len);
		memset(co,0,sizeof(co));
		//cout<<x<<" "<<i<<" "<<len<<endl;
		if(find(len)) dfs(i+1,len+1);
		f[nowans[len]]=0;
		nowans[len]=0;
	}
}
void work()
{
	for(int i=1;i<=N;i++)
		for(int j=M;j>=1;j--)
		{
			if(Dist(w[j],Bomb[i])<=R*R) {C[j][j][i]=1;D[i][j]=D[i][j+1];}
			else D[i][j]=j-1;
			for(int k=j+1;k<=M;k++) 
			{
				C[j][k][i]=C[j][k-1][i]&C[k][k][i];
				if(C[j][k][i]==1) maxl[j]=max(k,j);
			}
		}
	for(int i=M;i>=1;i--)
	{
		use[i]=maxn;
		for(int j=i;j<=M;j++)
			for(int k=1;k<=N;k++)
				if(C[i][j][k]==1)
				{
					use[i]=min(use[i],use[j+1]+1);
					break;
				}
	}
	for(int i=1;i<=M;i++)
		for(int j=1;j<=N;j++)
			maxl[i]=max(maxl[i],D[j][i]);
	for(int i=1;i<=M;i++) maxl[i]=max(maxl[i],i);
	dfs(1,1);
	printf("%d\n",ma);
	for(int i=1;i<=ma;i++) printf("%d ",ans[i]);
}
int main()
{
	freopen("zplhz.in","r",stdin);
	freopen("zplhz.out","w",stdout);
	read();
	work();
	return 0;
}