题目地址：http://acm.split.hdu.edu.cn/showproblem.php?pid=4435
思路：编号大的点应尽量避免建立加油站（2^0+2^1+2^2+......+2^i<2^(i+1)），所以先假设全部建站，若此时仍不能满足题意，则无解。否则，从n开始枚举点，尝试该点不建立加油站是否能满足题意（dist[i]表示节点i到最近加油站的距离，若i不为加油站则若dist[i]*2>d则不符合题意（从某加油站出发到i，从i并不能返回加油）。若i为加油站，则若从加油站1不能到达i，则不满足题意）。若不符合，则该点必须建立加油站。
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define debu
using namespace std;
const int maxn=150;
const int INF=0x3f3f3f3f;
int n,d;
queue<int> q;
int g[maxn][maxn];
int build[maxn],dist[maxn];
int v[maxn],x[maxn],y[maxn];
int Dist(int i,int j)
{
return ceil(sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])));
}
int bfs()
{
for(int i=1; i<=n; i++)
{
if(build[i]) dist[i]=0;
else dist[i]=INF;
}
memset(v,0,sizeof(v));
while(!q.empty()) q.pop();
q.push(1),v[1]=1;
while(!q.empty())
{
int now=q.front();
q.pop();
for(int i=1; i<=n; i++)
{
if(!v[i]&&g[now][i]<=d)
{
dist[i]=min(dist[i],dist[now]+g[now][i]);
if(build[i])
{
v[i]=1;
q.push(i);
}
}
}
}
for(int i=1; i<=n; i++)
{
if(build[i]&&!v[i]) return 0;
if(!build[i]&&dist[i]*2>d) return 0;
}
return 1;
}
void solve()
{
for(int i=1; i<=n; i++) build[i]=1;
if(!bfs())
{
printf("-1\n");
return ;
}
for(int i=n; i>=2; i--)
{
build[i]=0;
if(!bfs()) build[i]=1;
}
int pos=n;
while(!build[pos]) pos--;
for(int i=pos; i>=1; i--) printf("%d",build[i]);
printf("\n");
}
int main()
{
#ifdef debug
freopen("in.in","r",stdin);
#endif // debug
while(scanf("%d%d",&n,&d)!=EOF)
{
for(int i=1; i<=n; i++)
scanf("%d%d",&x[i],&y[i]);
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
g[i][j]=Dist(i,j);
solve();
}
return 0;
}
Hdu 4435 charge-station（BFS+贪心）
原文：http://blog.csdn.net/wang2147483647/article/details/52254334