转载请注明出处，谢谢http://blog.****.net/ACM_cxlove?viewmode=contents by---cxlove
题目：给出N个城市，从1开始需要遍历所有点，选择一些点建立加油站，使得花费最少
这题的特殊性在于他的花费上，2^(i-1)
利用一个非常重要的性质，2^0+2^1+2^2……+2^i<2^(i+1)
所有编号<=i的所有点都建，总花费比建一个还少。
这里就贪心一下，先假设所有点都建，然后依次从编号大的删点，看看能不能遍历整个图
dist[i]表示点i距离最近的一个加油站的距离
分析：突破口在于在i号点建立加油站的费用为2^i，这样特殊的花费会使得我们有一个贪心的规律，就是尽量不在号比较大的点建加油站，如果在n号点 建立加油站的费用会大于在除n以外的所有点都建加油站的总费用。所以我们可以先尝试把除n以外的所有点建立加油站，观察是否满足要求。若满足则说明我们必 然不会在n点建立加油站，若不满足我们就一定要在n点建加油站。若需要建，我们就建，然后就不用再考虑n点了，在确定了n点之后，我们用同样的方法来观察 n-1号点是否需要建立加油站，即将1~n-2号点都建立加油站，观察是否满足要求。以此类推，可以推出所有点的情况。
接下来我们需要解决对于一种给定的加油站建立情况，我们如何判断它是否满足题中的travel around的要求。分为两部判断，1.判断所有加油站是否可达（从1号点开始广搜，若到当前点距离<=d则入队）。2.判断其余点是否可达（刚才 的广搜过程可以顺便标出每个点到最近的加油站的距离，要求能从加油站到该点并返回加油站，所以点到加油站的距离必须小于等于d/2）。若满足这两点必然符 合要求，否则不符合要求。
2015-05-18：这里的dist维护的是到最近加油站的距离，要是最少肯定所有加油站都要路过
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
#define MOD 1000000007
const int INF=0x3f3f3f3f;
const double eps=1e-;
typedef long long ll;
#define cl(a) memset(a,0,sizeof(a))
#define ts printf("*****\n");
const int MAXN=;
int n,m,tt;
int c[MAXN][MAXN],ok[MAXN],vis[MAXN],dist[MAXN],d;
struct Node
{
int x,y;
void in()
{
scanf("%d%d",&x,&y);
}
}node[MAXN];
bool bfs()
{
queue<int> q;
cl(vis);
for(int i=;i<n;i++)
{
if(ok[i]) dist[i]=;
else dist[i]=INF;
}
int now;
q.push();
vis[]=;
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=;i<n;i++)
{
if(!vis[i]&&c[now][i]<=d)
{
dist[i]=min(dist[i],dist[now]+c[now][i]);
if(ok[i])
{
q.push(i);
vis[i]=;
}
}
}
}
for(int i=;i<n;i++)
{
if(ok[i]&&!vis[i]) return ;
if(!ok[i]&&dist[i]*>d) return ;
}
return ;
}
int main()
{
int i,j,k;
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
while(scanf("%d%d",&n,&d)!=EOF)
{
for(i=;i<n;i++)
{
node[i].in();
}
for(i=;i<n;i++)
{
for(j=;j<n;j++)
{
c[i][j]=ceil(sqrt((double)(node[i].x-node[j].x)*(node[i].x-node[j].x)+(node[i].y-node[j].y)*(node[i].y-node[j].y)));
}
}
for(i=;i<n;i++) ok[i]=;
if(!bfs())
{
puts("-1");
continue;
}
for(i=n-;i>;i--)
{
ok[i]=;
if(!bfs()) ok[i]=;
}
j=n-;
while(!ok[j]) j--;
for(i=j;i>=;i--) printf("%d",ok[i]);
puts("");
}
}