P1364 医院设置（Floyed）-白红宇

P1364 医院设置（Floyed）

阅读量：399 次

发布时间：2019-03-05

本文共 1692 字，大约阅读时间需要 5 分钟。

为了解决这个问题，我们需要找到一棵二叉树中建立医院的位置，使得所有居民到医院的距离之和最小。我们可以使用Floyd算法来计算所有节点之间的最短路径，从而确定最佳的医院位置。

方法思路

输入处理：读取输入数据，构建每个结点的左子节点和右子节点。

邻接矩阵初始化：使用一个邻接矩阵来表示树的结构，其中每个节点与其子节点之间的距离设为1。

Floyd算法：计算所有节点之间的最短路径。这个算法通过多次松弛操作，逐步更新所有节点对之间的最短路径。

计算最小总距离：对于每个节点作为医院位置，计算所有居民到该节点的距离之和，并找出最小的总和。

解决代码

#include 
   
    #include 
    
     #include 
     
      using namespace std;int main() {    int n;    cin >> n;    int pop[100 + 1];    int left[100 + 1];    int right[100 + 1];    int a[101][101]; // a[i][j] 表示i到j的最短距离    for (int i = 1; i <= n; ++i) {        int w, x, y;        cin >> w >> x >> y;        pop[i] = w;        if (x != 0) {            a[i][x] = 1;            a[x][i] = 1;        }        if (y != 0) {            a[i][y] = 1;            a[y][i] = 1;        }        a[i][i] = 0;    }    // Floyd算法计算所有点对的最短路径    for (int k = 1; k <= n; ++k) {        for (int i = 1; i <= n; ++i) {            for (int j = 1; j <= n; ++j) {                if (i != j && j != k) {                    if (a[i][j] > a[i][k] + a[k][j]) {                        a[i][j] = a[i][k] + a[k][j];                    }                }            }        }    }    // 计算每个节点作为医院时的总距离，并找最小值    int min_total = INT_MAX;    for (int k = 1; k <= n; ++k) {        int total = 0;        for (int v = 1; v <= n; ++v) {            if (v != k) {                total += a[k][v] * pop[v];            }        }        if (total < min_total) {            min_total = total;        }    }    cout << min_total << endl;    return 0;}