记录编号	93024	评测结果	AAAAAAAAAA
题目名称	[NOI 2003]智破连环阵	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.039 s
提交时间	2014-03-23 21:32:01	内存使用	0.59 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int SIZEN=200,INF=0x7fffffff/2;
class POINT{
public:
	int x,y;
};
int dist2(POINT a,POINT b){
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
POINT fort[SIZEN],bomb[SIZEN];//碉堡和炸弹
bool shoot[SIZEN][SIZEN]={0};//炸弹i是否能炸到碉堡j
int destroy[SIZEN][SIZEN]={0};//炸弹i从j开始能炸到哪
bool single[SIZEN][SIZEN]={0};//碉堡i~j能否被单发摧毁
vector<int> next[SIZEN];//这次从某一个点开始,本次轰炸的终点可能是哪些点
int minclear[SIZEN]={0};//清除从这个点~M至少需要几发
int M,n,K,K2;
void init(void){
	scanf("%d%d%d",&M,&n,&K);
	K2=K*K;
	for(int i=1;i<=M;i++) scanf("%d%d",&fort[i].x,&fort[i].y);
	for(int i=1;i<=n;i++) scanf("%d%d",&bomb[i].x,&bomb[i].y);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=M;j++){
			if(dist2(bomb[i],fort[j])<=K2) shoot[i][j]=true;
			else shoot[i][j]=false;
		}
	}
	for(int i=1;i<=n;i++){
		destroy[i][M+1]=M;
		for(int j=M;j>=1;j--){
			if(shoot[i][j]) destroy[i][j]=destroy[i][j+1],single[j][destroy[i][j]]=true;
			else destroy[i][j]=j-1;
		}
	}
	for(int i=1;i<=M;i++){
		for(int j=M;j>=i;j--){
			if(single[i][j]){
				for(int k=i;k<=j;k++) single[i][k]=true;
				break;
			}
		}
	}
	for(int i=1;i<=M;i++) for(int j=i;j<=M;j++) if(single[i][j]) next[i].push_back(j);
	minclear[M+1]=0;
	for(int i=M;i>=1;i--) minclear[i]=1+minclear[next[i].back()+1];
}
vector<int> c[SIZEN];
bool cn[SIZEN][SIZEN]={0};
int visit[SIZEN]={0};
int match[SIZEN]={0};
int nowplan[SIZEN]={0};//现在段对炸弹的对应
int ans=INF;
int oplan[SIZEN]={0};
void addseg(int u,int v,int pos){
	for(int i=1;i<=n;i++){
		for(int j=u;j>=1;j--){
			if(destroy[i][j]>=v) cn[pos][i]=true;
			if(destroy[i][j]>=v) c[pos].push_back(i);
		}
	}
}
int findpath(int x){
	for(int u=1;u<=n;u++){
		if(!cn[x][u]||visit[u]) continue;
		visit[u]=true;
		if(!match[u]||findpath(match[u])){
			match[u]=x;
			nowplan[x]=u;
			return u;
		}
	}
	return 0;
}
void DFS(int x,int used){//现在分了used段,编号小于x的碉堡均已爆破
	if(used+minclear[x]>=ans) return;
	if(x>M){
		ans=used;
		memset(oplan,0,sizeof(oplan));
		memcpy(oplan,nowplan,sizeof(oplan[0])*(n+1));
		return;
	}
	used++;
	c[used].clear();
	memset(cn[used],0,sizeof(cn[used]));
	for(int i=next[x].size()-1;i>=0;i--){
		int u=next[x][i];
		addseg(x,u,used);
		memset(visit,0,sizeof(visit));
		int nowp=findpath(used);
		if(nowp) DFS(u+1,used);
		match[nowplan[used]]=0;
		nowplan[used]=0;
	}
}
int main(){
	freopen("zplhz.in","r",stdin);
	freopen("zplhz.out","w",stdout);
	init();
	DFS(1,0);
	printf("%d\n",ans);
	for(int i=1;i<=ans;i++) printf("%d ",oplan[i]);
	printf("\n");
	return 0;
}