【CCF】最优配餐

问题描述
　　栋栋最近开了一家餐饮连锁店，提供外卖服务。随着连锁店越来越多，怎么合理的给客户送餐成为了一个急需解决的问题。
　　栋栋的连锁店所在的区域可以看成是一个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 广度优先搜索就可以，用visited[][] 标记访问过的坐标，把不能访问的坐标也标记成访问过的坐标就可以了。
统计一下订餐坐标的总数量，以判断结束与否。

当初提交时没有考虑n的范围，最终结果（100万）超出了int的范围，导致当初只有80分
具体原因类似于这个
提交为100分的代码如下，注释很详细：

#include <bits/stdc++.h> 
using namespace std;
const int N = 1005;    //最大大小 
const int DIRECTSIZE = 4;    //上下左右四个方向 
int order[N][N];     //某坐标位置的订单数
int visited[N][N] ;        //某坐标是否已经访问过 

struct direct{    //定义一个关于方向的结构体 
    int drow,dcol;
}direct[DIRECTSIZE] = {{-1,0},{1,0},{0,-1},{0,1}};

struct node{    //用于记录每个坐标走了多少步 
    int row,col,step;
    node(){}
    node(int r,int c,int s){row = r,col = c,step = s;}
};

queue<node> q;    // 定义一个node队列 
int coord = 0;    //总坐标数量 
long long ans = 0;    //这里需要使用long long，因为有些系统上 long int 和 int 是相同的

//广度优先搜索 
void bfs(int n){
    //v用来保存所有数据，包括走到某点坐标时的步数
    //front用以临时保存 
    node front,v;    
    //如果队列中有元素，就一直执行 
    while(!q.empty()){
        front = q.front();    //取出q中第一个元素
        q.pop();    //删除q中第一个元素 
        //搜索该点的四个方位 
        for(int i=0;i<DIRECTSIZE;i++){    //注意这里下标是从0开始的 
            v.row = direct[i].drow + front.row;    
            v.col = direct[i].dcol + front.col;
            v.step = front.step + 1; //坐标位置加一步
            
            //判断是否超出方格图大小 
            if(v.row < 1 || v.row > n || v.col < 1 || v.col > n) 
                continue;    //跳出本次循环
            //是否已经搜索过 
            if(visited[v.row][v.col]) 
                continue;    
            
            //如果有订单 
            if(order[v.row][v.col] != 0){
                //因为 每一个订单每走一个单位的距离需要花费1块钱 
                ans += v.step * order[v.row][v.col];    //有可能坐标点不止一个订单 
                visited[v.row][v.col] = 1;    //可以不加 
                coord--;        //坐标数减少 
                if(coord == 0)
                    return;    //结束 
            }
            
            //把搜索过的地点标记
            visited[v.row][v.col] = 1;
            //把没有走到头的v放进队列
            q.push(v);
        }    
    }
}


int main(){
    //freopen("input.txt","r",stdin);    //直接本地读取数据 
    
    int n,m,k,d,x,y,c;     //用以接收的变量 
    //初始化变量 
    memset(order,0,sizeof(order));
    memset(visited,0,sizeof(visited));
    //输入
    cin>>n>>m>>k>>d;
    for(int i=1;i<=m;i++){//输入分店坐标，分店坐标不能搜索 ，所以设置为true
        cin>>x>>y;
        q.push(node(x,y,0));    //把分店坐标压入队列中，以此为基础  //queue<node> q;  
        visited[x][y] = 1;
    } 
    for(int i=1;i<=k;i++) {
        cin>>x>>y;    //订单坐标
        cin>>c;     //该坐标订单数量 
        if(order[x][y] == 0)    //如果该坐标没有搜索过
             coord++;    //坐标数加1
        order[x][y] += c;    //把订单数赋给坐标位置 
    }
    for(int i=1;i<=d;i++) {
        cin>>x>>y;
        visited[x][y] = 1;    //把不能通过的也标记成已搜索 
    }
    
    //开启广度优先搜索 
    bfs(n);    
    
    cout<<ans<<endl; 
    
    return 0;
}

参考100分的方法：http://blog.csdn.net/tigerisland45/article/details/54945267

【CCF】最优配餐

评论 (0)