| 试题编号： | 201409-4 |
| 试题名称： | 最优配餐 |
| 时间限制： | 1.0s |
| 内存限制： | 256.0MB |
| 问题描述： | 问题描述 栋栋最近开了一家餐饮连锁店，提供外卖服务。随着连锁店越来越多，怎么合理的给客户送餐成为了一个急需解决的问题。 栋栋的连锁店所在的区域可以看成是一个n×n的方格图（如下图所示），方格的格点上的位置上可能包含栋栋的分店（绿色标注）或者客户（蓝色标注），有一些格点是不能经过的（红色标注）。 方格图中的线表示可以行走的道路，相邻两个格点的距离为1。栋栋要送餐必须走可以行走的道路，而且不能经过红色标注的点。 送餐的主要成本体现在路上所花的时间，每一份餐每走一个单位的距离需要花费1块钱。每个客户的需求都可以由栋栋的任意分店配送，每个分店没有配送总量的限制。 现在你得到了栋栋的客户的需求，请问在最优的送餐方式下，送这些餐需要花费多大的成本。 输入格式 输入的第一行包含四个整数n, m, k, d，分别表示方格图的大小、栋栋的分店数量、客户的数量，以及不能经过的点的数量。 接下来m行，每行两个整数xi, yi，表示栋栋的一个分店在方格图中的横坐标和纵坐标。 接下来k行，每行三个整数xi, yi, ci，分别表示每个客户在方格图中的横坐标、纵坐标和订餐的量。（注意，可能有多个客户在方格图中的同一个位置） 接下来d行，每行两个整数，分别表示每个不能经过的点的横坐标和纵坐标。 输出格式 输出一个整数，表示最优送餐方式下所需要花费的成本。 样例输入 10 2 3 3 1 1 8 8 1 5 1 2 3 3 6 7 2 1 2 2 2 6 8 样例输出 29 评测用例规模与约定 前30%的评测用例满足：1<=n <=20。 前60%的评测用例满足：1<=n<=100。 所有评测用例都满足：1<=n<=1000，1<=m, k, d<=n^2。可能有多个客户在同一个格点上。每个客户的订餐量不超过1000，每个客户所需要的餐都能被送到。 |
看到题目，首先想的是从店家到顾客进行bfs，动手写的时候突然想到如果从店家到顾客，那每个店家都要对每个顾客算距离，而从顾客到店家只用bfs到一个店家终止就可以了，当时还暗自窃喜，没想到入了另外一个坑。
先上 顾客到店家的代码，只得了60分
#include<iostream>
#include<vector>
#include<queue>
using namespace std;typedef struct{int x; //客户坐标x int y; //客户坐标y int deep; //距离当前坐标最近的分店的距离
}Ke; // 客户结构体 int status[1005][1005]={0}; // 标注每个点的状态，是分店 1，还是客户 2，还是不能经过的点 3 默认0
int map[1005][1005]={0}; // 如果是客户，存储每个点上客户需求量
int stamp[1005][1005]={0}; // 0表示未遍历，1表示正在队列中待遍历 2表示完全遍历 vector<Ke> vec; // 存储所有客户,便于后边计算 int n,m,k,d;// 注意，不能大于n 小于1 且status不能为3 边界值 // 此处从客户BFS找到最近的分店比较方便
int BFS(int x,int y){int i,j;// 重置遍历状态 for(i=0;i<=n;i++){for(j=0;j<=n;j++){stamp[i][j]=0;}}// 用3将地图包围起来，判断行不行得通的时候只用判断status是不是3即可,main中已实现 queue<Ke> que;Ke tmp1; tmp1.x=x;tmp1.y=y;tmp1.deep=0;que.push(tmp1);stamp[x][y]=1;while(que.size()>0){Ke tmp = que.front(); //cout<<tmp.x<<" "<<tmp.y<<" "<<tmp.deep<<endl;que.pop();// 左 if(status[tmp.x-1][tmp.y]==1)return tmp.deep+1;if(stamp[tmp.x-1][tmp.y]==0&&status[tmp.x-1][tmp.y]!=3){stamp[tmp.x-1][tmp.y]=1;Ke tmpxy ;tmpxy.x=tmp.x-1;tmpxy.y=tmp.y; tmpxy.deep = tmp.deep+1;que.push(tmpxy);}// 右 if(status[tmp.x+1][tmp.y]==1)return tmp.deep+1;if(stamp[tmp.x+1][tmp.y]==0&&status[tmp.x+1][tmp.y]!=3){stamp[tmp.x+1][tmp.y]=1;Ke tmpxy ;tmpxy.x=tmp.x+1;tmpxy.y=tmp.y; tmpxy.deep = tmp.deep+1;que.push(tmpxy);}// 上 if(status[tmp.x][tmp.y-1]==1)return tmp.deep+1;if(stamp[tmp.x][tmp.y-1]==0&&status[tmp.x][tmp.y-1]!=3){stamp[tmp.x][tmp.y-1]=1;Ke tmpxy ;tmpxy.x=tmp.x;tmpxy.y=tmp.y-1; tmpxy.deep = tmp.deep+1;que.push(tmpxy);}// 下 if(status[tmp.x][tmp.y+1]==1)return tmp.deep+1;if(stamp[tmp.x][tmp.y+1]==0&&status[tmp.x][tmp.y+1]!=3){stamp[tmp.x][tmp.y+1]=1;Ke tmpxy ;tmpxy.x=tmp.x;tmpxy.y=tmp.y+1; tmpxy.deep = tmp.deep+1;que.push(tmpxy);}stamp[tmp.x][tmp.y]=2; }}int main(){cin>>n>>m>>k>>d;int x,y,t;// 用3将地图包围起来，判断行不行得通的时候只用判断status是不是3即可for(int i=0;i<=n+1;i++){status[0][i]=3; status[n+1][i]=3; status[i][0]=3; status[i][n+1]=3;}// 输入分店 for(int i=0;i<m;i++){cin>>x>>y; status[x][y] = 1;}// 输入客户 Ke tmp;for(int i=0;i<k;i++){cin>>x>>y>>t; status[x][y] = 2; // 如果该点需求量为0，则新加客户 ,否则不新加客户 if(map[x][y]==0){tmp.x=x;tmp.y=y; vec.push_back(tmp);} map[x][y]+=t;}for(int i=0;i<d;i++){cin>>x>>y; status[x][y] = 3;}long long result=0;//for(int i=0;i<n+3;i++){for(int j=0;j<n+3;j++)cout<<status[i][j]<<" ";cout<<endl;}for(int i=0;i<vec.size();i++){tmp = vec[i];long long len = BFS(tmp.x,tmp.y);//cout<<tmp.x<<tmp.y<<len<<"\t\txxx"<<endl;;result+=len*map[tmp.x][tmp.y];}cout<<result<<endl;return 0;
}
做完提交超时只有60分，想不出更简单的方法，网上看了一下别人的思路，才发现从店家到顾客遍历才行。于是写了一遍从店家到顾客（依次以每个店家坐标为起始对整个图做bfs），最后也只是得了90分。后来才发现这个遍历还有个巧处，同时将分店同时加到bfs的初始队列中进行遍历，这点很妙。
代码：
#include<iostream>
#include<vector>
#include<queue>
using namespace std;typedef struct node{int x; //客户坐标x int y; //客户坐标y int deep; //距离当前坐标最近的分店的距离 node(int a=0,int b=0,int c=0){x=a;y=b;deep=c;}
}Ke; // 客户结构体 ,也可以用来保存分店坐标此时deep无意义 short status[1005][1005]={0}; // 标注每个点的状态，是分店 1，还是客户 2，还是不能经过的点 3 默认0
int map[1005][1005]={0}; // 如果是客户，存储每个点上客户需求量
short stamp[1005][1005]={0}; // 0表示未遍历，1表示正在队列中待遍历 2表示完全遍历
int minLen[1005][1005]; // 表示每个点距离最近的店的距离， 初始化时要弄到最大 int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};vector<Ke> vec; // 存储所有客户,便于后边计算总花费
vector<Ke> dian; // 存储所有分店，作为遍历的起点 int n,m,k,d;// 注意，不能大于n 小于1 且status不能为3 边界值
void BFS(){int i,j;int keCount = 0;// 重置遍历状态 for(i=0;i<=n;i++){for(j=0;j<=n;j++){stamp[i][j]=0;}}// 用3将地图包围起来，判断行不行得通的时候只用判断status是不是3即可for(int i=0;i<=n+1;i++){status[0][i]=3; status[n+1][i]=3; status[i][0]=3; status[i][n+1]=3;}queue<Ke> que;for(i=0;i<dian.size();i++){que.push(dian[i]);}while(que.size()>0&&keCount<=k){Ke tmp = que.front(); //cout<<tmp.x<<" "<<tmp.y<<" "<<tmp.deep<<endl;que.pop();int deep = tmp.deep;for(i=0;i<4;i++){int x = tmp.x+dir[i][0];int y = tmp.y+dir[i][1];if(stamp[x][y]==0&&status[x][y]!=3){stamp[x][y] = 1;minLen[x][y] = deep+1;que.push(Ke(x,y,deep+1));if(status[x][y]==2)keCount++;}}stamp[tmp.x][tmp.y]=2;}}int main(){cin>>n>>m>>k>>d;int x,y,t;Ke tmp;// 初始化每个点距离最近点的距离为最大值for(int i=0;i<=n+1;i++){for(int j=0;j<=n+1;j++) minLen[i][j] = 1000000;}// 输入分店 for(int i=0;i<m;i++){cin>>x>>y; status[x][y] = 1;tmp.x=x;tmp.y=y; dian.push_back(tmp);}// 输入客户 for(int i=0;i<k;i++){cin>>x>>y>>t; status[x][y] = 2; // 如果该点需求量为0，则新加客户 ,否则不新加客户 if(map[x][y]==0){tmp.x=x;tmp.y=y; vec.push_back(tmp);} map[x][y]+=t;}for(int i=0;i<d;i++){cin>>x>>y; status[x][y] = 3;}long long result=0;BFS();for(int i=0;i<vec.size();i++){tmp = vec[i];result+=minLen[tmp.x][tmp.y]*map[tmp.x][tmp.y];}cout<<result<<endl;return 0;
}