L3-005. 垃圾箱分布

大家倒垃圾的时候，都希望垃圾箱距离自己比较近，但是谁都不愿意守着垃圾箱住。所以垃圾箱的位置必须选在到所有居民点的最短距离最长的地方【此处为第一重排序选择的条件】，同时还要保证每个居民点都在距离它一个不太远的范围内。

现给定一个居民区的地图，以及若干垃圾箱的候选地点，请你推荐最合适的地点。如果解不唯一，则输出到所有居民点的平均距离最短的那个解【此处为第二重排序的原则】。如果这样的解还是不唯一，则输出编号最小的地点【此处为第三重排序的原则，尽管遍历的时候是按顺序的，但sort排序的时候不是有序进行比较的（具体自己百度sort百度原理），所以比较加上这条！】。

输入格式：

输入第一行给出4个正整数：N（<= 10³）是居民点的个数【在这里也WA了一次，因为编号是123的时候就需要来一个while循环进行字符串转数字了】；M（<= 10）是垃圾箱候选地点的个数；K（<= 10⁴）是居民点和垃圾箱候选地点之间的道路的条数；D_S是居民点与垃圾箱之间不能超过的最大距离【这里不用double来存贮其实也是可以过的，WA了第六遍的时候我以为是数据超int了需要用double来存，貌似是无用的】。所有的居民点从1到N编号，所有的垃圾箱候选地点从G1到GM编号。

随后K行，每行按下列格式描述一条道路：
P1 P2 Dist
其中P1和P2是道路两端点的编号，端点可以是居民点，也可以是垃圾箱候选点。Dist是道路的长度，是一个正整数。

输出格式：

首先在第一行输出最佳候选地点的编号。然后在第二行输出该地点到所有居民点的最小距离和平均距离。数字间以空格分隔，保留小数点后1位。如果解不存在，则输出“No Solution”。

AC代码：题目一般吧，细节仔细都能考虑到的。

 #include<iostream>

 #include<stdio.h>

 #include<string.h>

 #include<math.h>

 #include<algorithm>

 #include<queue>

 #include<set>

 #include<vector>

 #include<string>

 #include<stack>

 #define  inf 0x3f3f3f3f

 #define  dinf 0x7fffffff*1.0

 using namespace std;   //L3-005,垃圾箱，16:50--

 #define N 1200

 #define ll long long

 struct node{

     int x;

     double d;

     node(int x=,double d=0.0):x(x),d(d){}

 };

 struct node1{

     int id;

     double minn,ave;

     node1(int id=,double minn=-,double ave=-):id(id),minn(minn),ave(ave){}

 }ans[];

 //1--到所有居民点的最短距离 相比较最长的地方,2-相等时，按平均距离最短的那个解

 bool cmp(node1 a,node1 b){

     if(fabs(a.minn-b.minn)<1e-){

         if(fabs(a.ave-b.ave)<1e-)

             return a.id<b.id;

         else

             return a.ave<b.ave;

     }

     else

         return a.minn>b.minn;

 }

 vector<node>G[N];//垃圾箱就是把垃圾箱自身编号加上N

 double dis[N];

 int vis[N];

 int n,m,k;

 double ds;//一个阈值

 int cnt;

 void debug(int num){

     printf("gar:%d--",num);double s=;

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

         s+=dis[i];

         printf(" %.0lf",dis[i]);

     }

     cout<<"  s: "<<s<<endl;

 }

 void spfa(int ed){

     queue<int>Q;

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

         dis[i]=dinf;

     memset(vis,,sizeof(vis));

     Q.push(ed);

     int u,v;

     dis[ed]=0.0;

     while(Q.size()>){

         u=Q.front();Q.pop();

         vis[u]=;

         for(int i=;i<(int)G[u].size();i++){

             v=G[u][i].x;

             if(dis[v]>dis[u]+G[u][i].d){

                 dis[v]=dis[u]+G[u][i].d;

                 if(!vis[v]){

                     Q.push(v);

                     vis[v]=;

                 }

             }

         }

     }

     double minn=dinf;

     double sum=0.0;

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

         if(dis[i]>ds)return ;

         sum+=dis[i];

         minn=min(minn,dis[i]);

     }

     ans[++cnt]=node1(ed,minn,sum/(1.0*n) );

 }

 int fact(char ch[]){

     int x=,i=;

     if(ch[]=='G'){

        i=;

     }

     while(ch[i]!='\0'){

         x =x*+ch[i]-'' ;

         i++;

     }

     if(ch[]=='G')x+=n;

     return x;

 }

 int main(){

     char ch1[],ch2[];

     while(scanf("%d%d%d%lf",&n,&m,&k,&ds)!=EOF){

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

             G[i].clear();

         cnt=;//统计加入ans结构体的个数

         int x,y;

         double dist;

         for(int i=;i<=k;i++){

             scanf("%s%s%lf",ch1,ch2,&dist);

             x=fact(ch1);

             y=fact(ch2);

             G[x].push_back(node(y,dist));

             G[y].push_back(node(x,dist));

         }

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

             spfa(i);

         if(cnt==){

             printf("No Solution\n");

         }

         else{

             sort(ans+,ans++cnt,cmp);

              printf("G%d\n",ans[].id-n);

              printf("%.1lf %.1lf\n",ans[].minn,ans[].ave);

         }

     }

     return ;

 }

（这题没有负权环，数据量真的水，所以无论用那种最短路算法都可以——我用的spfa算法）

巴特西

【最短路+较复杂处理】PAT-L3-005. 垃圾箱分布

L3-005. 垃圾箱分布

最新文章

热门文章