一个用C语言编写的村庄医院选址问题

ExistentStarts

问题n 个村庄之间的交通图可以用有向网图来表示，图中边<vi, vj>上的权值表示从村庄
i 到村庄 j 的道路长度。现在要从这 n 个村庄中选择一个村庄新建一所医院，问这所医院
应建在哪个村庄，才能使所有的村庄离医院都比较近？
为简单起见，我们使用-1 来代表无穷大（∞）。
输入说明：
第 1 行是一个整数 N，表示村庄数（20 以内）
后面是 N 阶邻接矩阵，用 -1 表示无穷大
输出要求：顺序输出 N 个村庄的偏心度，用-1 表示无穷大，每个数字后跟一个空格分隔
【输入样例】
5
0 1 -1 -1 -1
-1 0 2 -1 -1
-1 -1 0 2 4
-1 1 3 0 -1
-1 -1 -1 5 0
【输出样例】
-1 6 8 5 7
实现代码，用Floyd算法写的，涉及图的结构
#include <stdio.h>

#define N 20
#define INF -1

void floydWarshall(int graph[N][N], int n) {
    int i, j, k;
    for (k = 0; k < n; k++) {
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                if (graph[i][k] != INF && graph[k][j] != INF &&
                    (graph[i][j] == INF || graph[i][k] + graph[k][j] < graph[i][j])) {
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }
}

void printEccentricities(int graph[N][N], int n) {
        int i,j;
    int eccentricity, maxEccentricity;
    for ( i = 0; i < n; i++) {
        maxEccentricity = 0;
        for ( j = 0; j < n; j++) {
            if (graph[i][j] > maxEccentricity) {
                maxEccentricity = graph[i][j];
            }
        }
        printf("%d ", maxEccentricity);
    }
}

int main() {
    int n, graph[N][N];
        int i,j;
    // 读取村庄数和邻接矩阵
    scanf("%d", &n);
    for ( i = 0; i < n; i++) {
        for ( j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }

    // 使用 Floyd-Warshall 算法计算最短路径
    floydWarshall(graph, n);

    // 输出村庄的偏心度
    //printEccentricities(graph, n);
   

    return 0;
}
/*感觉写的有问题，但又不知道那里错了，反正输出样例没对*/

vethenc

帮忙排版一下代码

#include <stdio.h>

#define N 20
#define INF -1

void floydWarshall(int graph[N][N], int n) {
    int i, j, k;
    for (k = 0; k < n; k++) {
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                if (graph[i][k] != INF && graph[k][j] != INF &&
                    (graph[i][j] == INF || graph[i][k] + graph[k][j] < graph[i][j])) {
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }
}

void printEccentricities(int graph[N][N], int n) {
        int i,j;
    int eccentricity, maxEccentricity;
    for ( i = 0; i < n; i++) {
        maxEccentricity = 0;
        for ( j = 0; j < n; j++) {
            if (graph[i][j] > maxEccentricity) {
                maxEccentricity = graph[i][j];
            }
        }
        printf("%d ", maxEccentricity);
    }
}

int main() {
    int n, graph[N][N];
        int i,j;
    // 读取村庄数和邻接矩阵
    scanf("%d", &n);
    for ( i = 0; i < n; i++) {
        for ( j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }

    // 使用 Floyd-Warshall 算法计算最短路径
    floydWarshall(graph, n);

    // 输出村庄的偏心度
    //printEccentricities(graph, n);

    return 0;
}

许我浅笑而安°

Floyd最短路径

yyzzy

没有运行效果图呀

FruitBaby

最短路径算法，

fireshark

贪心算法求最优解

w507710214

许我浅笑而安° 发表于 2023-12-1 23:04
Floyd最短路径

你好大佬，看到了你的天猫精灵用mtkclient破解的教程，想请教一些问题，就是我的一个手机魅族mx6，目前变砖了，只能使用mtkclient识别到分区，也可以像你教程中写的那样读写分区，我想给我这个手机适配一个第三方的recovery，对应的分区就是recovery分区，但是我不太明白这个分区他读出来是bin格式的文件，但是如果我能适配到适合我手机的第三方recovery，这个recovery的格式却是.img格式的请问下这能像您那个文章里写的那样把后缀img改成bin刷入分区吗？我试了下这个并不能开机，是不是不能直接改成bin而需要做些处理呢？

许我浅笑而安°

w507710214 发表于 2023-12-18 06:07
你好大佬，看到了你的天猫精灵用mtkclient破解的教程，想请教一些问题，就是我的一个手机魅族mx6，目前变 ...

不行,rec不能直接这么装,不是一个单独分区的镜像,建议找找资料按教程来