hdu 4435 第37届ACM/ICPC天津现场赛E题

转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

题目：给出N个城市，从1开始需要遍历所有点，选择一些点建立加油站，使得花费最少

这题的特殊性在于他的花费上，2^(i-1)

利用一个非常重要的性质，2^0+2^1+2^2……+2^i<2^(i+1)

所有编号<=i的所有点都建，总花费比建一个还少。

这里就贪心一下，先假设所有点都建，然后依次从编号大的删点，看看能不能遍历整个图

dist[i]表示点i距离最近的一个加油站的距离

分析：突破口在于在i号点建立加油站的费用为2^i，这样特殊的花费会使得我们有一个贪心的规律，就是尽量不在号比较大的点建加油站，如果在n号点建立加油站的费用会大于在除n以外的所有点都建加油站的总费用。所以我们可以先尝试把除n以外的所有点建立加油站，观察是否满足要求。若满足则说明我们必然不会在n点建立加油站，若不满足我们就一定要在n点建加油站。若需要建，我们就建，然后就不用再考虑n点了，在确定了n点之后，我们用同样的方法来观察 n-1号点是否需要建立加油站，即将1~n-2号点都建立加油站，观察是否满足要求。以此类推，可以推出所有点的情况。

接下来我们需要解决对于一种给定的加油站建立情况，我们如何判断它是否满足题中的travel around的要求。分为两部判断，1.判断所有加油站是否可达（从1号点开始广搜，若到当前点距离<=d则入队）。2.判断其余点是否可达（刚才的广搜过程可以顺便标出每个点到最近的加油站的距离，要求能从加油站到该点并返回加油站，所以点到加油站的距离必须小于等于d/2）。若满足这两点必然符合要求，否则不符合要求。

2015-05-18：这里的dist维护的是到最近加油站的距离，要是最少肯定所有加油站都要路过

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 #include<map>

 using namespace std;

 #define MOD 1000000007

 const int INF=0x3f3f3f3f;

 const double eps=1e-;

 typedef long long ll;

 #define cl(a) memset(a,0,sizeof(a))

 #define ts printf("*****\n");

 const int MAXN=;

 int n,m,tt;

 int c[MAXN][MAXN],ok[MAXN],vis[MAXN],dist[MAXN],d;

 struct Node

 {

     int x,y;

     void in()

     {

         scanf("%d%d",&x,&y);

     }

 }node[MAXN];

 bool bfs()

 {

     queue<int> q;

     cl(vis);

     for(int i=;i<n;i++)

     {

         if(ok[i])   dist[i]=;

         else dist[i]=INF;

     }

     int now;

     q.push();

     vis[]=;

     while(!q.empty())

     {

         now=q.front();

         q.pop();

         for(int i=;i<n;i++)

         {

             if(!vis[i]&&c[now][i]<=d)

             {

                 dist[i]=min(dist[i],dist[now]+c[now][i]);

                 if(ok[i])

                 {

                     q.push(i);

                     vis[i]=;

                 }

             }

         }

     }

     for(int i=;i<n;i++)

     {

         if(ok[i]&&!vis[i])  return ;

         if(!ok[i]&&dist[i]*>d) return ;

     }

     return ;

 }

 int main()

 {

     int i,j,k;

     #ifndef ONLINE_JUDGE

     freopen("1.in","r",stdin);

     #endif

     while(scanf("%d%d",&n,&d)!=EOF)

     {

         for(i=;i<n;i++)

         {

             node[i].in();

         }

         for(i=;i<n;i++)

         {

             for(j=;j<n;j++)

             {

                 c[i][j]=ceil(sqrt((double)(node[i].x-node[j].x)*(node[i].x-node[j].x)+(node[i].y-node[j].y)*(node[i].y-node[j].y)));

             }

         }

         for(i=;i<n;i++)    ok[i]=;

         if(!bfs())

         {

             puts("-1");

             continue;

         }

         for(i=n-;i>;i--)

         {

             ok[i]=;

             if(!bfs())  ok[i]=;

         }

         j=n-;

         while(!ok[j])      j--;

         for(i=j;i>=;i--)   printf("%d",ok[i]);

         puts("");

     }

 }

巴特西

hdu 4435 第37届ACM/ICPC天津现场赛E题

最新文章

热门文章