洛谷P3884 [JLOI2009] 二叉树问题(c嘎嘎）

题目链接：P3884 [JLOI2009] 二叉树问题 - 洛谷 | 计算机科学教育新生态
题目难度：普及/提高

做题心得：一开始看到这道题想着求深度和宽度还要求距离好麻烦，深度得用dfs，宽度得用bfs，求距离还要用图论的floyd算法太麻烦了，就想着有啥好方法，最后迫于实力菜去看了题解，果然题解都是大神，做法都很巧妙，本题借用一个大佬的思路。

解题思路：首先用链接矩阵存图，由于题目中说节点 u,vu,v 之间的距离表示从 uu 到 vv 的最短有向路径上向根节点的边数的两倍加上向叶节点的边数，所以父亲到儿子节点距离为1所以求深度只要求根节点到所有节点距离的最大值即可，宽度的话用桶来记录每一层的节点个数，最后遍历桶来求最大宽度。

最后奉上代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 110,INX = 0x3f3f3f3f;
int d[N][N];//邻接矩阵存图
int sum[100000];
int n;

void floyd()//floyd算法 
{
for(int k=1; k <= n; k++)
   for(int i=1; i <= n; i++)
      for(int j=1; j <= n ; j++)
      {
        d[i][j] = min(d[i][j],d[i][k] + d[k][j]);
  }
} 
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    cin >> n;
    for(int i=1; i<=n; i++)
       for(int j=1; j<=n; j++)
       {
           if(i == j) d[i][j] = 0;
           else d[i][j] = INX;
   }//初始化 

int m = n-1;
while(m--)
{
int u,v;
cin >> u >> v;
d[u][v] = 1;//父亲到儿子距离为1 
d[v][u] = 2;//儿子到父亲距离为2 
} 
floyd();

int x,y;
cin >> x >> y;//要求指定节点之间的距离 

int hight = -100000,width = -100000;
int maxn = 0; 
for(int i=2; i<=n; i++)
{
hight = max(hight,d[1][i]);//深度
sum[d[1][i]] ++;//统计每一层的节点个数 
maxn = max(maxn,d[i][1]);
}
for(int i=1; i<=maxn; i++)
{
width = max(width,sum[i]);//求宽度 
}

cout<<hight+1<<'\n';//加上根节点 
cout<<width<<'\n';//宽度
cout<<d[x][y]<<'\n';//距离
 
    return 0;
}

原文地址：https://blog.csdn.net/2302_79431881/article/details/144429889

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！