给我们n个坐标点和一个距离d，表示车开m米就没油了。
然后要选几个点建立油站，使得能够从1出发遍历所有的点，然后回到1。 并且规定1这个点必须有油站，在第i个点建立油站的费用是 2^(i-1)
因为费用的特殊性质，如果最大的点能够不建立，那么肯定是不建的。 所以首先在所有的点建立油站，看是否可以遍历所有的点，然后依次从大到小枚举点，看是否可以不建立油站。
但是卡在如何判断是否能够遍历所有的点上。
首先判断，所有的油站距离最近的油站的距离不能超过d, 如果超过就不能到达，而且也不能通过没有油站的点中转
然后，不是油站的点距离最近的油站的距离不能超过d/2 ，这个很显然，如果超过d/2，那么从油站到达这个点，就没办法回去了。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 /* 10 花费是2^(i-1) 这个很特殊 11 如何高效得判断是否能经过所有的点然后回家？ 12 */ 13 const int INF = 1<<30; 14 const int N = 128 + 10; 15 struct Point 16 { 17 int x,y; 18 double dist(const Point &rhs) 19 { 20 return sqrt( (x-rhs.x)*(x-rhs.x)+(y-rhs.y)*(y-rhs.y) ); 21 } 22 }a[N]; 23 int n,d; 24 int dist[N][N]; 25 int sta[N]; 26 bool vis[N]; 27 int cnt1,cnt2; 28 bool bfs() 29 { 30 memset(vis,0,sizeof(vis)); 31 int tmp = 0; 32 for(int i=1;i<=n;++i) 33 tmp += sta[i]; 34 cnt1 = 1; 35 cnt2 = 0; 36 vis[1] = true; 37 queue q; 38 q.push(1); 39 while(!q.empty()) 40 { 41 int u = q.front();q.pop(); 42 for(int i=2;i<=n;++i) 43 { 44 if(!sta[i]) continue; 45 if(!vis[i] && dist[u][i]<=d) 46 { 47 q.push(i); 48 cnt1++; 49 vis[i] = true; 50 } 51 } 52 } 53 for(int i=1;i<=n;++i) 54 if(sta[i]) q.push(i); 55 while(!q.empty()) 56 { 57 int u = q.front(); q.pop(); 58 for(int i=2;i<=n;++i) 59 { 60 if(sta[i]) continue; 61 if(!vis[i] && dist[u][i]*2<=d) 62 { 63 vis[i] = true; 64 cnt2++; 65 } 66 } 67 } 68 if(cnt1==tmp && cnt2==n-tmp) return true; 69 70 return false; 71 } 72 int main() 73 { 74 //freopen("d:/in.txt","r",stdin); 75 while(scanf("%d%d",&n,&d)!=EOF) 76 { 77 for(int i=1;i<=n;++i) 78 { 79 scanf("%d%d",&a[i].x,&a[i].y); 80 sta[i] = true; 81 } 82 for(int i=1;i<=n;++i) 83 { 84 for(int j=1;j<=n;++j) 85 dist[i][j] = dist[j][i] = (int)ceil(a[i].dist(a[j])); 86 } 87 if(bfs()) 88 { 89 90 for(int i=n;i>=2;--i) 91 { 92 sta[i] = false; 93 if(!bfs()) 94 sta[i] = true; 95 } 96 while(sta[n]==0) n--; 97 for(int i=n;i>=1;--i) 98 printf("%d",sta[i]); 99 puts("");100 }101 else102 puts("-1");103 }104 return 0;105 }