题目‘点击打开链接
’是一个修加油站的题目；
要求能够能够到达每个城市，并且能够回到初始点，车走路的耗油距离是有限的 ，必须在油用完之前加油，
如果不能到就输出-1，否则输出建加油站的钱（以二进制形式输出），i处建站，用钱2的i-1次方；（求最小建站花费）
所以规律，ok【i】数组，如果建站就输出1，不建就输出0；（倒叙输出，因为是从大到小）
当时并没有任何思路；
看了看题解思路是真的奇妙：
就是现在每个点都进行建站，然后从花钱最多站开始去除，（如果全部建站都不行，就是-1） 除到最少建站数就是最少建站花费；
dis数组存从当前点到最近的加油站的距离，判断分两个方面：
1.如果当前点也有加油站，dis[i] <= D就可以;
2.如果当前点决定不建立加油站，那么dis[i]要小于D/2;
不符合要求就不能拆这个加油站。
代码，注意细节
#include <iostream> #include<algorithm> #include<string> #include<cstdio> #include<cstring> #include<cmath> #include<queue> using namespace std; const int maxn=150; const int inf=0x3f3f; int dis[maxn]; int vis[maxn]; int e[maxn][maxn]; int ok[maxn]; int n,d; struct node { int x,y; node(int xx=0,int yy=0){x=xx;y=yy;} }; node s[maxn]; double getdis(int i,int j) { return sqrt((s[i].x-s[j].x)*(s[i].x-s[j].x)+(s[i].y-s[j].y)*(s[i].y-s[j].y)); } bool dfs() { memset(vis,0,sizeof(vis)); for(int i=0;i<n;i++) { if(ok[i])//如果建站 耗费距离是0 dis[i]=0; else dis[i]=inf; } //cout<<dis[2]<<endl; //dis[0]=0; vis[0]=1; queue<int> q; q.push(0); while(q.size()) { int u=q.front(); q.pop(); for(int i=0;i<n;i++) //更新每个点求最小行进距离（距离最近加油站） { if(e[u][i]<=d&&!vis[i]) //注意= { dis[i]=min(dis[i],dis[u]+e[u][i]); if(ok[i]) {q.push(i); vis[i]=1;//为何要ok时才标记走过，因为不是加油站就需要继续进行更新最小值，加油站就不用了，因为他dis值为0 } } } } for(int i=0;i<n;i++) { if(ok[i]&&!vis[i]) //如果是加油站却从1到不了，那返回错误 return false; if(!ok[i]&&dis[i]*2>d)//别写dis[i]>(double)d/2了 ，如果不是加油站，到最近加油站的来回距离还大于d/2 ，那也不行 return false; } return true; } void solve() { for(int i=0;i<n;i++) //标记所有加油站 ok[i]=1; if(!dfs()) //全部加油站都不行 { cout<<"-1"<<endl; return ; } for(int i=n-1;i>=0;i--) { ok[i]=0; if(!dfs()) //如果不行就在此处有站 ok[i]=1; } int j=n-1; while(ok[j]==0)j--; //去除前导0 for(int i=j;i>=0;i--) cout<<ok[i]; cout<<endl; } int main() { while(cin>>n>>d) { for(int i=0;i<n;i++) { cin>>s[i].x>>s[i].y; } for(int i=0;i<n;i++) for(int j=0;j<n;j++) { e[i][j]=ceil(getdis(i,j));//求两点间距离 } solve(); } // cout << "Hello world!" << endl; return 0; }引子 博客点击打开链接
