/* 题意:给定每个点在平面内的坐标,要求选出一些点,在这些点建立加油站,使得总花费最少(1号点必须建立加油站)。在i点建立加油站需要花费2^i。 建立加油站要求能使得汽车从1点开始走遍全图所有的点并回到1点,途中汽车加油次数不限,每个加油站的使用次数不限, 但是汽车油箱有上限d(加满油可以跑距离d)。 第i个点的费用=比i小的点的所有费用和+1; 所以从后向前判断,如果当前点不为加油站在这个点前面的所有都为加油站的话,判断是否成立 如果不能成立的话,这个点必选,否则不用必须选 */ #include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<queue> #include<algorithm> #include<iostream> using namespace std; #define eps 1e-10 #define inf 0x3fffffff #define N 200 int ma[N][N]; struct node { double x,y; } f[N*N]; int n,m; int distan(int i,int j) { return ceil(sqrt((f[i].x- f[j].x)*(f[i].x-f[j].x) + (f[i].y - f[j].y)*(f[i].y-f[j].y))); } int vis[N]; int bfs(int x) { int i,k,viss[N],num=1; memset(viss,0,sizeof(viss)); queue<int>q; q.push(1); viss[1]=1; while(!q.empty()) { k=q.front(); q.pop(); for(i=2; i<=n; i++) { if(i==k||viss[i])continue; if(vis[i]==0&&ma[k][i]*2<=m) { num++; viss[i]=1; } if(vis[i]&&ma[k][i]<=m) { num++; viss[i]=1; q.push(i); } if(num==n) return 1; } } return 0; } int main() { int i,j,k; while(scanf("%d%d",&n,&m)!=EOF) { for(i=1; i<=n; i++) scanf("%lf%lf",&f[i].x,&f[i].y); for(i=1; i<=n-1; i++) for(j=i+1; j<=n; j++) { k=distan(i,j); ma[i][j]=ma[j][i]=k; } for(i=1; i<=n; i++) vis[i]=1; if(!bfs(n+1)) { printf("-1 "); continue; } for(i=n; i>=2; i--) { vis[i]=0; if(!bfs(i)) vis[i]=1; // printf("%d ",vis[i]); } i=n; while(vis[i]==0) i--; for(; i>=1; i--) { if(vis[i]) printf("1"); else printf("0"); } printf(" "); } return 0; }