Gas Station
A gas station has to be built at such a location that the minimum distance between the station and any of the residential housing is as far away as possible. However it must guarantee that all the houses are in its service range.
Now given the map of the city and several candidate locations for the gas station, you are supposed to give the best recommendation. If there are more than one solution, output the one with the smallest average distance to all the houses. If such a solution is still not unique, output the one with the smallest index number.
题意超复杂的一道题 我整理了一下 意思差不多是这样
1.算出每个加油站到所有house的距离
2.所有距离必须小于 加油站的最大服务距离
3.从所有距离找出一个最小距离
4.在每个加油站的最小距离中取最大的距离
5.若最小距离相等则取平均距离最小的
6.若平均距离最小则取序号最小的
以上为这题的步骤 是不是快晕了? 算法应该还是简单的 就是 dijkstra算法
下面给出AC代码
1 #include <stdio.h> 2 #include <stdlib.h> 3 #define MAX 1000000 4 5 6 int g[1011][1011]; 7 int N,M,K,Ds; 8 int dis[1011]; 9 int flag[1011]; 10 float sum[10]; 11 12 void dijkstra(int v) 13 { 14 int i,j,pos,min; 15 dis[v]=0; 16 17 for(i=1;i<=N+M;i++) 18 { 19 min=MAX; 20 for(j=1;j<=N+M;j++) 21 { 22 if(flag[j]!=1 && dis[j]<min) 23 { 24 min=dis[j]; 25 pos=j; 26 } 27 } 28 flag[pos]=1; 29 for(j=1;j<=N+M;j++) 30 { 31 if(flag[j]!=1) 32 { 33 if(dis[pos]+g[pos][j]<dis[j]) 34 { 35 dis[j]=dis[pos]+g[pos][j]; 36 } 37 } 38 } 39 40 } 41 } 42 int main() 43 { 44 int i,j; 45 int s3,s4,L,k,pos=0,t=0,flag1=0; 46 int min[10]; 47 float ave,ave2,max; 48 char s1[10],s2[10]; 49 50 scanf("%d%d%d%d",&N,&M,&K,&Ds); 51 for(i=1;i<=N+M;i++) 52 { 53 dis[i]=MAX; 54 for(j=1;j<=N+M;j++) 55 g[i][j]=MAX; 56 } 57 for(i=1;i<=K;i++) 58 { 59 scanf("%s %s%d",s1,s2,&L); 60 61 if(s1[0]=='G') 62 s3=atoi(s1+1)+N; 63 else 64 s3=atoi(s1); 65 if(s2[0]=='G') 66 s4=atoi(s2+1)+N; 67 else 68 s4=atoi(s2); 69 g[s3][s4]=g[s4][s3]=L; 70 } 71 72 for(i=N+1;i<=N+M;i++) 73 { 74 dijkstra(i); 75 min[t]=dis[1]; 76 for(j=1;j<=N;j++) 77 { 78 if(dis[j]>Ds) 79 { 80 min[t]=-1; 81 sum[t]=-1; 82 break; 83 } 84 if(min[t]>dis[j]) 85 { 86 min[t]=dis[j]; 87 } 88 sum[t]+=dis[j]; 89 } 90 t++; 91 for(j=1;j<=N+M;j++) 92 { 93 dis[j]=MAX; 94 flag[j]=0; 95 } 96 } 97 for(i=0;i<M;i++) 98 { 99 if(min[i]!=-1) 100 { 101 flag1=1; 102 break; 103 104 } 105 } 106 max=-100000; 107 for(i=0;i<M;i++) 108 { 109 if(flag1==0) 110 break; 111 if(max<min[i]&&min[i]!=-1) 112 { 113 max=min[i]; 114 pos=i; 115 ave=sum[pos]/N; 116 } 117 else if(max==min[i]&&min[i]!=-1) 118 { 119 ave=sum[pos]/N; 120 ave2=sum[i]/N; 121 if(ave>ave2) 122 { 123 max=min[i]; 124 pos=i; 125 ave=ave2; 126 } 127 128 } 129 } 130 if(flag1==1) 131 printf("G%d/n%.1f %.1f/n",pos+1,max,ave); 132 else 133 printf("No Solution/n"); 134 }