LAO LAO捞捞
查看原帖
LAO LAO捞捞
866969
telankesi楼主2023/4/22 10:16
#include <stdio.h>
#include <string.h>
#include <math.h>
int n;
int g[10002][10002];//路径距离
int b[1000000];//每一个路径下,同层的宽度
int min(int x, int y) {
    return x < y ? x : y;
}
int main() {
    scanf("%d", &n);
    int x, y;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            if (i != j)
                g[i][j] = 1e9;
    }
    for (int i = 1; i <= n-1; i++) {

        scanf("%d %d", &x, &y);
        g[x][y] = g[y][x] = 1;

    }

    scanf("%d %d", &x, &y);
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            if (k == i)continue;
            for (int j = 1; j <= n; j++) {

        g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
    int r;//路径
    if (g[x][1] + g[1][y] == g[x][y])r = g[x][1] * 2 + g[1][y];
    else if (x < y)r = g[x][y];
    else r = g[x][y] * 2;
    int h=0;//深度
    int l=0;//宽度

    for (int i = 1; i <= n; i++) {
        if (h < g[1][i]+1)h = g[1][i] + 1;
        b[g[1][i]]++;
    }
    for (int i = 0; i <=h ; i++) {
        if (l < b[i] )l = b[i] ;
    }

    printf("%d\n%d\n%d", h, l, r);
    return 0;
}
2023/4/22 10:16
加载中...