试题历届试题邮局

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

　　C村住着n户村民，由于交通闭塞，C村的村民只能通过信件与外界交流。为了方便村民们发信，C村打算在C村建设k个邮局，这样每户村民可以去离自己家最近的邮局发信。

　　现在给出了m个备选的邮局，请从中选出k个来，使得村民到自己家最近的邮局的距离和最小。其中两点之间的距离定义为两点之间的直线距离。

输入格式

　　输入的第一行包含三个整数n, m, k，分别表示村民的户数、备选的邮局数和要建的邮局数。
　　接下来n行，每行两个整数x, y，依次表示每户村民家的坐标。
　　接下来m行，每行包含两个整数x, y，依次表示每个备选邮局的坐标。
　　在输入中，村民和村民、村民和邮局、邮局和邮局的坐标可能相同，但你应把它们看成不同的村民或邮局。

输出格式

　　输出一行，包含k个整数，从小到大依次表示你选择的备选邮局编号。（备选邮局按输入顺序由1到m编号）

样例输入

5 4 2
0 0
2 0
3 1
3 3
1 1
0 1
1 0
2 1
3 2

样例输出

2 4

数据规模和约定

　　对于30%的数据，1<=n<=10，1<=m<=10，1<=k<=5；
　　对于60%的数据，1<=m<=20；
　　对于100%的数据，1<=n<=50，1<=m<=25，1<=k<=10。

思路

　　这题首先想到的就是dfs，每个邮局都有两个状态：选或不选，当选择的邮局数刚好为k个时，求出最小距离和，与ans比较，若比ans更小，那么就将选择的这组邮局记录在数组flag中，于是代码如下（超时）——

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <algorithm>
 6 #define INF 0x3f3f3f3f
 7 #define zero 1e-7
 8 
 9 using namespace std;
10 typedef long long ll;
11 
12 struct node {
13     int x, y;
14 }cm[55], yj[30];//村民、邮局的坐标
15 
16 int n, m, k;//村民户数，备选邮局数，要建的邮局数
17 double d[55][30];//村民到各邮局的距离
18 bool vis[30];//标记邮局是否被选择
19 double ans=INF;//最小距离和
20 int flag[15];//记录选择的邮局
21 
22 void init() {
23     for(int i=0; i<n; i++)
24         cin>>cm[i].x>>cm[i].y;
25     for(int i=0; i<m; i++)
26         cin>>yj[i].x>>yj[i].y;
27     for(int i=0; i<n; i++)
28         for(int j=0; j<m; j++)
29             d[i][j]=sqrt((cm[i].x-yj[j].x)*(cm[i].x-yj[j].x)+(cm[i].y-yj[j].y)*(cm[i].y-yj[j].y));
30 }
31 
32 void dfs(int t, int cnt) {//考虑第t个邮局，当前选出的邮局数
33     if(cnt==k) {//若已选出k个邮局
34         double sum=0;
35         for(int i=0; i<n; i++) {
36             double mind=INF;//村民i到邮局的最短距离
37             for(int j=0; j<t; j++) {
38                 if(vis[j] && d[i][j]<mind)
39                     mind=d[i][j];
40             }
41             sum+=mind;
42         }
43         if(sum<ans) {//若当前最短距离和小于ans，则更新ans和flag[]
44             int c=0;
45             for(int i=0; i<t; i++) {
46                 if(vis[i]) flag[c++]=i+1;
47             }
48             ans=sum;
49         }
50         return;
51     }
52     if(m-t==k-cnt) {//若刚好剩下k-cnt个邮局，则必须全都选上
53         for(int i=t; t<m; t++) vis[i]=true;
54         dfs(m, k);
55         for(int i=t; t<m; t++) vis[i]=false;//回溯
56         return;
57     }
58     vis[t]=true;
59     dfs(t+1, cnt+1);//选择邮局t
60     vis[t]=false;//回溯
61     dfs(t+1, cnt);//不选择邮局t
62 }
63 
64 int main() {
65     cin>>n>>m>>k;
66     init();
67     dfs(0, 0);
68     for(int i=0; i<k; i++) {
69         cout<<flag[i]<<' ';
70     }
71     return 0;
72 }

　　这样暴力深搜的结果就是最后两组测试用例超时了，只有80分，那么就需要再进行剪枝. 惭愧的是，我不知道该怎么剪了^。。。于是只好百度求助各路大神，最后敲中这位博主的详解，循序渐进，步步升级，谁都能看懂(๑•̀ㅂ•́)و✧→click here.

经过点拨，便发现还可以做如下优化：

1. 维护一个记录居民到已选邮局的最短距离的数组minlen[n]；

2. 维护一个记录当前已选邮局的向量（vector）v；还需设置一个外部向量（vector）flag 以记录最优组合方案；

3. 用数组vis[]标记不能起到缩小距离作用的邮局；

　　先完成前两步优化，代码如下——

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <vector>
 6 #include <algorithm>
 7 #define INF 0x3f3f3f3f
 8 #define zero 1e-7
 9 
10 using namespace std;
11 typedef long long ll;
12 
13 struct node {
14     int x, y;
15 }cm[55], yj[30];//村民、邮局的坐标
16 
17 int n, m, k;//村民户数，备选邮局数，要建的邮局数
18 double d[55][30];//村民到各邮局的距离
19 double ans=INF;//最小距离和
20 vector<int> flag;//存储最优选择方案
21 
22 void init() {
23     for(int i=0; i<n; i++)
24         cin>>cm[i].x>>cm[i].y;
25     for(int i=0; i<m; i++)
26         cin>>yj[i].x>>yj[i].y;
27     for(int i=0; i<n; i++)
28         for(int j=0; j<m; j++)
29             d[i][j]=sqrt((cm[i].x-yj[j].x)*(cm[i].x-yj[j].x)+(cm[i].y-yj[j].y)*(cm[i].y-yj[j].y));
30 }
31 //考虑第t个邮局，当前选出的邮局数，当前存储的居民到邮局的最短距离，当前已选择的邮局
32 void dfs(int t, int cnt, double minlen[], vector<int> v) {
33     if(cnt==k) {//若已选出k个邮局
34         double sum=0;
35         for(int i=0; i<n; i++) {
36             sum+=minlen[i];
37         }
38         if(sum<ans) {//若当前最短距离和小于ans，则更新ans和flag
39             ans=sum;
40             flag=v;
41         }
42         return;
43     }
44     if(m-t<k-cnt) return;//选不够k个邮局了，直接返回
45     if(t<m && cnt<k) {//当前邮局存在 且 还未选满
46         double temp[55];
47         memcpy(temp, minlen, sizeof(temp));
48         bool ok=false;
49         for(int i=0; i<n; i++) {
50             if(d[i][t]<temp[i]) {
51                 temp[i]=d[i][t];
52                 ok=true;
53             }
54         }
55         //选择邮局t
56         if(ok) {
57             v.push_back(t+1);
58             dfs(t+1, cnt+1, temp, v);
59             v.pop_back();//回溯
60         }
61         //不选择邮局t
62         dfs(t+1, cnt, minlen, v);
63     }
64 }
65 
66 int main() {
67     cin>>n>>m>>k;
68     init();
69     double minlen[55];
70     for(int i=0; i<n; i++) minlen[i]=INF;
71     vector<int> v;
72     dfs(0, 0, minlen, v);
73     for(int i=0; i<k; i++) {
74         cout<<flag[i]<<' ';
75     }
76     return 0;
77 }

　　到这步就90分了，还有最后一组测试用例超时没过，接着再进行第三步优化.

　　于是修改后代码如下（不知为何，设置为先不选择邮局t 进行深搜后就会错，实在找不出原因来，下面的代码是错的，一个测试用例都过不了，如有路过的大神能指点迷津，实在感激不尽~~~）——

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <vector>
 6 #include <algorithm>
 7 #define INF 0x3f3f3f3f
 8 #define zero 1e-7
 9 
10 using namespace std;
11 typedef long long ll;
12 
13 struct node {
14     int x, y;
15 }cm[55], yj[30];//村民、邮局的坐标 
16 
17 int n, m, k;//村民户数，备选邮局数，要建的邮局数 
18 double d[55][30];//村民到各邮局的距离 
19 bool vis[30];//标记邮局是否起到缩小距离作用 
20 double ans=INF;//最小距离和 
21 vector<int> flag;//存储最优选择方案 
22 
23 void init() {
24     for(int i=0; i<n; i++) 
25         cin>>cm[i].x>>cm[i].y;
26     for(int i=0; i<m; i++) 
27         cin>>yj[i].x>>yj[i].y;
28     for(int i=0; i<n; i++) 
29         for(int j=0; j<m; j++) 
30             d[i][j]=sqrt((cm[i].x-yj[j].x)*(cm[i].x-yj[j].x)+(cm[i].y-yj[j].y)*(cm[i].y-yj[j].y));
31 }
32 //考虑第t个邮局，当前选出的邮局数，当前存储的居民到邮局的最短距离，当前已选择的邮局 
33 void dfs(int t, int cnt, double minlen[], vector<int> v) { 
34     if(cnt==k) {//若已选出k个邮局 
35         double sum=0;
36         for(int i=0; i<n; i++) 
37             sum+=minlen[i];
38         if(sum<ans) {//若当前最短距离和小于ans，则更新ans和flag 
39             ans=sum;
40             flag=v;
41         }
42         return;
43     }
44     if(m-t<k-cnt) return;//选不够k个邮局了，直接返回 
45     if(t<m) { 
46         //不选择邮局t
47         dfs(t+1, cnt, minlen, v);
48         if(vis[t]) return;//若邮局t已标记为不可选，那么直接return 
49         bool ok=false;
50         for(int i=0; i<n; i++) {
51             if(d[i][t]<minlen[i]) {
52                 minlen[i]=d[i][t];
53                 ok=true;
54             }
55         }
56         //选择邮局t
57         if(ok) {
58             v.push_back(t+1);
59             dfs(t+1, cnt+1, minlen, v);
60             v.pop_back();//回溯 
61         }
62         else vis[t]=true;//标记为无法起到缩小距离作用，即不可选状态 
63     }
64 }
65 
66 int main() {
67     cin>>n>>m>>k;
68     init();
69     double minlen[55];
70     for(int i=0; i<n; i++) minlen[i]=INF; 
71     vector<int> v;
72     dfs(0, 0, minlen, v);
73     for(int i=0; i<k; i++) 
74         cout<<flag[i]<<' ';
75     return 0;
76 }

试题 历届试题 邮局

试题历届试题邮局