文章

11

粉丝

216

获赞

4

访问

103.1k

头像
用满多叉树来解决树的最短路径问题
P1492 北京航空航天大学2019年机试题
发布于2021年2月25日 22:14
阅读数 11.0k

#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>

using namespace std;

/*
思路:
    构建满三叉树,满三叉树结点i的祖先结点为 fa = (i + 1)/3;
    lchild = fa * 3 - 1 ; michild = fa * 3; rchild = fa * 3 + 1;
    通过回溯来寻找最短路径,回溯一次,路径长度加一;
    并在此过程记录各自的回溯路径;拼接即可得最终路径
*/
struct node
{
    int data;
    int pr;
} sk[100];

int triTree[1005]; //满三叉树
map<int, int> inde;  //建立结点的data到满三叉树的index的映射
int p1[100], p2[100]; //用于存储以两个端结点为起点的回溯路径
int len1, len2;

bool cmp(node a, node b)
{
    return a.pr < b.pr;
}

//找最短路径
void spl(int n, int m)   //n,m为端点结点在满三叉树中的下标索引
{
    p1[0] = triTree[n];
    p2[0] = triTree[m];
    len1 = 1; len2 = 1;

    while (n != m)
    {
        if (n > m)
        {
            n = (n + 1) / 3;
            p1[len1++] = triTree[n];
        }
        else
        {
            m = (m + 1) / 3;
            p2[len2++] = triTree[m];
        }
    }
    len1-- ;  //交汇点重复
}

//输出路径
v...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发