1.题目描述：点击打开链接
2.解题思路：本题利用DFS解决。不过本题的解法颇为巧妙，注意到2^0+2^1+…+2^(i-1)<2^i，这就意味着即使在0~i-1都建立加油站，费用也会小于单独在i处建立加油站。这就提示我们，可以一开始全部都建立加油站，然后从大到小依次尝试着删除加油站，如果可以删除，就删除，如果不可以，再添加上。那么该如何判断删除第i处之后是否可行呢？可以利用dfs判断，如果当前访问结点u是建立过加油站的，如果它的邻接点v也是建立了加油站的，且dist(u,v)<=d，那么就可以去访问v，或者邻接点v没有建立加油站，但是dist(u,v)<=d/2，此时也可以去访问v，，因为只要满足dist(u,v)<=d/2，那么就一定可以从v沿着路径u-v访问到任意结点。这样，进行完dfs后，如果仍然有结点没有被访问过，那么说明删除操作是不可行的，需要恢复。
3.代码：
#include<iostream>#include<algorithm>#include<cassert>#include<string>#include<sstream>#include<set>#include<bitset>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<cctype>#include<functional>#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;#define me(s) memset(s,0,sizeof(s))#define rep(i,n) for(int i=0;i<(n);i++)typedef long long ll;typedef unsigned int uint;typedef unsigned long long ull;typedef pair <int, int> P;const int N=200;double d;int n;int vis[N],mark[N];struct Point{double x,y;Point (){}Point (double x,double y):x(x),y(y){}}p[N];double dist(Point a,Point b){double dx=a.x-b.x;double dy=a.y-b.y;return ceil(sqrt(dx*dx+dy*dy));}void dfs(int u){vis[u]=1;for(int i=1;i<n;i++)if(!vis[i]){if(mark[u]&&mark[i]&&dist(p[u],p[i])<=d)dfs(i);else if(mark[u]&&!mark[i]&&dist(p[u],p[i])<=d/2)dfs(i);}}bool judge(){me(vis);vis[0]=1;dfs(0);for(int i=0;i<n;i++)if(!vis[i]) //仍然有结点没有被访问过，则该次删除不可行return false;return true;}int main(){while(~scanf("%d%lf",&n ,&d)){rep(i,n)scanf("%lf%lf",&p[i].x,&p[i].y);rep(i,n)mark[i]=1;if(!judge()){puts("-1");continue;}for(int i=n-1;i>=1;i–){mark[i]=0;if(!judge())mark[i]=1;}int first=1;for(int i=n-1;i>=0;i–)if(first&&mark[i]){printf("%d",mark[i]);first=0;}else if(!first)printf("%d",mark[i]);cout<<endl;}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
谦受益，满招损。
