HDU 4435 charge-station(12年天津)
题目：给出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++)
{
