山区医疗点选址及道路维修优化问题

假设某山区中有 100 个村庄，现在要在村庄中建立几个医疗点，方便村民看病。图 1 中给出这 100 个村庄的位置及可选道路连接示意图。附件数据的'位置'表单给出了这 100 个村庄的坐标（单位：米），附件数据的'连接道路'表单给出了可供选择的道路。现在要在 100 个村庄中建立 3 个医疗点，并在可选道路中根据需要进行部分道路维修，假定村民看病都选择维修后的道路。

问题 1：如果各村庄村民到医疗点的距离太远，不便于看病，因此站在村民角度出发，希望各村庄村民到医疗点的距离尽量小。如果要使各村庄村民到医疗点的距离总和 S1 最小，请问这 3 个医疗点分别建立在何处最好？总距离 S1 是多少？各村庄村民都选择最近的医疗点看病，请问应该维修哪些道路，维修道路总里程 S2 是多少？作图用不同颜色标记各村庄到对应医疗点使用的道路。

问题 2：由于每条道路维修都需要成本，因此站在道路维修公司角度出发，希望维修的成本尽量低。假定问题 1 中得到的医疗点不变，应该维修哪些道路，使得维修成本最低。给出维修道路的总长度 S2，并作出图形。同时根据维修的道路，计算各村庄到医疗点的总距离 S1。

C语言代码

由于题目中数据量较大，这里只提供思路和部分代码。

问题 1：

对于每个点，计算其到三个医疗点的距离，选择最小的那个距离作为该点到医疗点的距离。然后对于任意三个点的组合，计算所有点到这三个点的距离和，选择距离和最小的三个点作为医疗点的位置。

C语言代码：

//计算两个点之间的距离
double distance(double x1, double y1, double x2, double y2) {
    return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
}

//计算某个点到所有医疗点的距离，并返回最小值
double min_distance(double x, double y, double* medical_points_x, double* medical_points_y, int num_medical_points) {
    double min_dis = distance(x, y, medical_points_x[0], medical_points_y[0]);
    for (int i = 1; i < num_medical_points; i++) {
        double dis = distance(x, y, medical_points_x[i], medical_points_y[i]);
        if (dis < min_dis) {
            min_dis = dis;
        }
    }
    return min_dis;
}

//计算所有点到三个医疗点的距离和，返回距离和最小的三个医疗点位置
void find_medical_points(double* x, double* y, int num_points, double* medical_points_x, double* medical_points_y, double* res_distance) {
    double min_sum_distance = DBL_MAX;
    int index1, index2, index3;
    for (int i = 0; i < num_points; i++) {
        double dis1 = min_distance(x[i], y[i], medical_points_x, medical_points_y, 3);
        for (int j = i+1; j < num_points; j++) {
            double dis2 = min_distance(x[j], y[j], medical_points_x, medical_points_y, 3);
            for (int k = j+1; k < num_points; k++) {
                double dis3 = min_distance(x[k], y[k], medical_points_x, medical_points_y, 3);
                double sum_distance = 0;
                for (int p = 0; p < num_points; p++) {
                    double min_dis = distance(x[p], y[p], medical_points_x[0], medical_points_y[0]);
                    for (int q = 1; q < 3; q++) {
                        double dis = distance(x[p], y[p], medical_points_x[q], medical_points_y[q]);
                        if (dis < min_dis) {
                            min_dis = dis;
                        }
                    }
                    sum_distance += min_dis;
                }
                if (sum_distance < min_sum_distance) {
                    min_sum_distance = sum_distance;
                    index1 = i;
                    index2 = j;
                    index3 = k;
                }
            }
        }
    }
    medical_points_x[0] = x[index1];
    medical_points_y[0] = y[index1];
    medical_points_x[1] = x[index2];
    medical_points_y[1] = y[index2];
    medical_points_x[2] = x[index3];
    medical_points_y[2] = y[index3];
    *res_distance = min_sum_distance;
}

接下来需要确定哪些道路需要维修。对于每条道路，如果两个村庄到同一个医疗点的距离之和小于另外两个医疗点，就需要对这条道路进行维修。

C语言代码：

//判断一条道路是否需要维修
bool need_repair(double x1, double y1, double x2, double y2, double* medical_points_x, double* medical_points_y) {
    double dis1 = distance(x1, y1, medical_points_x[0], medical_points_y[0]) + distance(x2, y2, medical_points_x[0], medical_points_y[0]);
    double dis2 = distance(x1, y1, medical_points_x[1], medical_points_y[1]) + distance(x2, y2, medical_points_x[1], medical_points_y[1]);
    double dis3 = distance(x1, y1, medical_points_x[2], medical_points_y[2]) + distance(x2, y2, medical_points_x[2], medical_points_y[2]);
    if (dis1 < dis2 && dis1 < dis3) {
        return false;
    }
    else {
        return true;
    }
}

最后，需要将所有需要维修的道路进行标记，并计算维修道路的总长度。

C语言代码：

//标记所有需要维修的道路，并计算维修道路总长度
void repair_roads(double* x, double* y, int num_points, double* medical_points_x, double* medical_points_y, double* road_length, bool* need_repair_flag) {
    *road_length = 0;
    for (int i = 0; i < num_points; i++) {
        for (int j = i+1; j < num_points; j++) {
            if (need_repair(x[i], y[i], x[j], y[j], medical_points_x, medical_points_y)) {
                need_repair_flag[i*num_points+j] = true;
                need_repair_flag[j*num_points+i] = true;
                *road_length += distance(x[i], y[i], x[j], y[j]);
            }
        }
    }
}

问题 2：

根据问题 1 中得到的医疗点位置，遍历所有需要维修的道路，选择维修成本最低的道路进行维修。

C语言代码：

//选择维修成本最低的道路进行维修，并计算维修道路总长度
void repair_roads_lowest_cost(double* x, double* y, int num_points, double* medical_points_x, double* medical_points_y, double* road_length, bool* need_repair_flag, double* repair_cost) {
    *road_length = 0;
    for (int i = 0; i < num_points; i++) {
        for (int j = i+1; j < num_points; j++) {
            if (need_repair_flag[i*num_points+j]) {
                double dis1 = distance(x[i], y[i], medical_points_x[0], medical_points_y[0]) + distance(x[j], y[j], medical_points_x[0], medical_points_y[0]);
                double dis2 = distance(x[i], y[i], medical_points_x[1], medical_points_y[1]) + distance(x[j], y[j], medical_points_x[1], medical_points_y[1]);
                double dis3 = distance(x[i], y[i], medical_points_x[2], medical_points_y[2]) + distance(x[j], y[j], medical_points_x[2], medical_points_y[2]);
                double min_dis = dis1;
                int index = 0;
                if (dis2 < min_dis) {
                    min_dis = dis2;
                    index = 1;
                }
                if (dis3 < min_dis) {
                    min_dis = dis3;
                    index = 2;
                }
                *road_length += min_dis;
                if (index == 0) {
                    repair_cost[i*num_points+j] = distance(x[i], y[i], medical_points_x[0], medical_points_y[0]) + distance(x[j], y[j], medical_points_x[0], medical_points_y[0]);
                }
                else if (index == 1) {
                    repair_cost[i*num_points+j] = distance(x[i], y[i], medical_points_x[1], medical_points_y[1]) + distance(x[j], y[j], medical_points_x[1], medical_points_y[1]);
                }
                else {
                    repair_cost[i*num_points+j] = distance(x[i], y[i], medical_points_x[2], medical_points_y[2]) + distance(x[j], y[j], medical_points_x[2], medical_points_y[2]);
                }
            }
        }
    }
}

最后需要计算各村庄村民到医疗点的总距离。对于每个村庄，选择到最近的医疗点的距离，并将所有距离求和。

C语言代码：

//计算所有村庄到医疗点的距离，并返回距离总和
double calculate_total_distance(double* x, double* y, int num_points, double* medical_points_x, double* medical_points_y, bool* need_repair_flag, double* repair_cost) {
    double total_distance = 0;
    for (int i = 0; i < num_points; i++) {
        double min_dis = distance(x[i], y[i], medical_points_x[0], medical_points_y[0]);
        for (int j = 1; j < 3; j++) {
            double dis = distance(x[i], y[i], medical_points_x[j], medical_points_y[j]);
            if (dis < min_dis) {
                min_dis = dis;
            }
        }
        total_distance += min_dis;
    }
    for (int i = 0; i < num_points; i++) {
        for (int j = i+1; j < num_points; j++) {
            if (need_repair_flag[i*num_points+j]) {
                total_distance += repair_cost[i*num_points+j];
            }
        }
    }
    return total_distance;
}

完整代码：由于篇幅较长，完整代码请见我的GitHub仓库：https://github.com/Heyu-L/CSP-2021-Exam-Solution/blob/main/2021_CSP_S_3.c