今天做天津题的时候感觉特别困,思路也没想清楚,一开始以为是费用流,后来发现有贪心的性质,枚举验证就可以了,但是不知道怎么去验证,之前写了个dfs,但是由于每个点不止能经过一次,所以过不了样例,看了题解后才知道要从源点开始判断到其他点的距离,如果到一个非加油站的点的距离小于等于d的话这个点就是可到达的,如果到一个加油站距离小于d的话也可以到达。之前一直没想到这个性质,伤不起……
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> using namespace std; bool vis[150],ans[150]; int map[150][150],pre[150]; double pos[150][2]; int n,d,tot; void dfs(int k) { if(ans[k]) { for(int i=1;i<=n;i++) { if(!vis[i]) { if(ans[i]) { if(map[k][i]<=d) { vis[i]=true; tot++; dfs(i); } } else if(2*map[k][i]<=d) { vis[i]=true; tot++; } } } } } int main() { //freopen("input.txt","r",stdin); while(scanf("%d%d",&n,&d)!=EOF) { for(int i=1;i<=n;i++) { scanf("%lf%lf",&pos[i][0],&pos[i][1]); for(int j=1;j<i;j++) { double dis=sqrt((pos[i][0]-pos[j][0])*(pos[i][0]-pos[j][0])+(pos[i][1]-pos[j][1])*(pos[i][1]-pos[j][1])); int temp=dis; if(dis-temp>10e-8) temp++; map[i][j]=map[j][i]=temp; } } memset(ans,-1,sizeof(ans)); bool ok=false; for(int i=n;i>=0;i--) { if(i==1) continue; memset(vis,0,sizeof(vis)); tot=1; vis[1]=true; ans[i]=false; dfs(1); if(tot!=n) ans[i]=true; else ok=true; } if(!ok) { printf("-1\n"); continue; } while(!ans[n]) n--; for(int i=n;i>=1;i--) if(ans[i]) printf("1"); else printf("0"); printf("\n"); } }