題目：給出N個城市，從1開始需要遍歷所有點，選擇一些點建立加油站，使得花費最少
http://acm.hdu.edu.cn/showproblem.php?pid=4435
這題的特殊性在於他的花費上，2^(i-1)
利用一個非常重要的性質，2^0+2^1+2^2……+2^i<2^(i+1)
所有編號<=i的所有點都建，總花費比建一個還少。
這裡就貪心一下，先假設所有點都建，然後依次從編號大的刪點，看看能不能遍歷整個圖
dist[i]表示點i距離最近的一個加油站的距離
[cpp]
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<queue>
#define inf 1<<30
#define M 2005
#define N 130
#define maxn 300005
#define eps 1e-10
#define zero(a) fabs(a)<eps
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define lson step<<1
#define rson step<<1|1
#define MOD 1000000009
#define sqr(a) ((a)*(a))
#define Key_value ch[ch[root][1]][0]
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
struct Point
{
int x,y;
}p[N];
int n,d;
int path[N][N];
int ok[N];
double dist(int i,int j)
{
return sqrt((double)sqr(p[i].x-p[j].x)+sqr(p[i].y-p[j].y));
}
bool bfs()
{
bool vis[N];
int dist[N];
queue<int>que;
mem(vis,false);
for(int i=0;i<n;i++)
{
//本身是加油站，距離是0
if(ok[i]) dist[i]=0;
else dist[i]=inf;
}
que.push(0);vis[0]=true;
while(!que.empty())
{
int u=que.front();
que.pop();
for(int i=0;i<n;i++)
{
if(!vis[i]&&path[u][i]<=d)
{
dist[i]=min(dist[i],dist[u]+path[u][i]);
if(ok[i])
{
que.push(i);
vis[i]=true;
}
}
}
}
for(int i=0;i<n;i++)
{
//雖然本身是個加油站，但是從1出發根本到不了
if(ok[i]&&!vis[i]) return false;
//不是一個加油站，不能保證從一個有加油站的地方來回
if(!ok[i]&&dist[i]*2>d) return false;
}
return true;
}
void slove()
{
for(int i=0;i<n;i++) ok[i]=1;
if(!bfs()) {puts("-1");return ;} //全部都建還不能遍歷
for(int i=n-1;i>0;i--)
{
ok[i]=0;
if(!bfs()) ok[i]=1;
}
int j=n-1;
while(!ok[j]) j--;
for(int i=j;i>=0;i--) printf("%d",ok[i]);
puts("");
}
int main()
{
while(scanf("%d%d",&n,&d)!=EOF)
{
for(int i=0;i<n;i++) scanf("%d%d",&p[i].x,&p[i].y);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
path[i][j]=ceil(dist(i,j));
}
}
slove();
}
return 0;
}
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<queue>
#define inf 1<<30
#define M 2005
#define N 130
#define maxn 300005
#define eps 1e-10
#define zero(a) fabs(a)<eps
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define lson step<<1
#define rson step<<1|1
#define MOD 1000000009
#define sqr(a) ((a)*(a))
#define Key_value ch[ch[root][1]][0]
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
struct Point
{
int x,y;
}p[N];
int n,d;
int path[N][N];
int ok[N];
double dist(int i,int j)
{
return sqrt((double)sqr(p[i].x-p[j].x)+sqr(p[i].y-p[j].y));
}
bool bfs()
{
bool vis[N];
int dist[N];
queue<int>que;
mem(vis,false);
for(int i=0;i<n;i++)
{
//本身是加油站，距離是0
if(ok[i]) dist[i]=0;
else dist[i]=inf;
}
que.push(0);vis[0]=true;
while(!que.empty())
{
int u=que.front();
que.pop();
for(int i=0;i<n;i++)
{
if(!vis[i]&&path[u][i]<=d)
{
dist[i]=min(dist[i],dist[u]+path[u][i]);
if(ok[i])
{
que.push(i);
vis[i]=true;
}
}
}
}
for(int i=0;i<n;i++)
{
//雖然本身是個加油站，但是從1出發根本到不了
if(ok[i]&&!vis[i]) return false;
//不是一個加油站，不能保證從一個有加油站的地方來回
if(!ok[i]&&dist[i]*2>d) return false;
}
return true;
}
void slove()
{
for(int i=0;i<n;i++) ok[i]=1;
if(!bfs()) {puts("-1");return ;} //全部都建還不能遍歷
for(int i=n-1;i>0;i--)
{
ok[i]=0;
if(!bfs()) ok[i]=1;
}
int j=n-1;
while(!ok[j]) j--;
for(int i=j;i>=0;i--) printf("%d",ok[i]);
puts("");
}
int main()
{
while(scanf("%d%d",&n,&d)!=EOF)
{
for(int i=0;i<n;i++) scanf("%d%d",&p[i].x,&p[i].y);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
path[i][j]=ceil(dist(i,j));
}
}
slove();
}
return 0;
}
