HDU 4435 charge-station(12年天津)
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
题目：给出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距离最近的一个加油站的距离
#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;}