смертельный 2022-10-22 20:54 采纳率: 50%
浏览 182
已结题

数据结构程序设计实践-收费

问题遇到的现象和发生背景

算法与数据结构

★实验任务

有一张无限大的图,图中的节点编号从1开始。图中节点由无向边连接,编号为i的节点分别与2i号节点和2i+1号节点连接,显然任意两个点之间的最短路是确定的且唯一的。最开始每条边上的花费都是0。 接下来有两种操作

给从u到v的最短路上的每条边都加上w的花费

计算走最短路从u到v的总花费(即路上所有边的花费和)

★数据输入

第一行输入一个整数q,表示操作的数量,接下来q行,每行第一个数字代表操作的类型,如果是1号操作,则紧接着输入u,v,w三个整数;如果是2号操作,接着输入u,v两个整数。

★数据输出

对于每一个2号操作,输出一行一个数字,代表路上的总花费

输入示例
7
1 3 4 30
1 4 1 2
1 3 6 8
2 4 3
1 6 1 40
2 3 7
2 2 4
输出示例
94
0
32
★数据范围

50% : q <= 10, 1≤u,v,w≤1000

100% : q <= 1000, 1≤u,v≤1000000,w <= 1e9

我的解答思路和尝试过的方法

毫无思路,没有学习图的话,如何通过树来完成呢?

  • 写回答

2条回答 默认 最新

  • Lg_970 2022-10-25 00:14
    关注

    傻子做法:

    
    #include <bits/stdc++.h>
    using namespace std;
    
    const int N=1e6+10;
    int treee[N];
    int sum=0,flag=0;
    
    int find_public_father(int u,int v){
        int t1=1,t2=1,arr1[10000],arr2[10000];
        arr1[0]=u; arr2[0]=v;
        while(u>1){
            u/=2;
            arr1[t1++]=u;
        }
        while(v>1){
            v/=2;
            arr2[t2++]=v;
        }
        for(int i=0;i<t1;i++){
            for(int j=0;j<t2;j++){
                if(arr1[i]==arr2[j]){
                    return arr1[i];
                }
            }
        }
    }
    
    void add(int u,int v,int w){
        if(u==v){
            flag=1;
            return;
        }else if(u>v){
            return;
        }
        add(2*u,v,w);
        if(flag){
            treee[2*u]+=w;
            return;
        }
        add(2*u+1,v,w);
        if(flag){
            treee[2*u+1]+=w;
            return;
        }
    }
    
    void travel(int u,int v){
        if(u==v){
            flag=1;
            return;
        }else if(u>v){
            return;
        }
        travel(2*u,v);
        if(flag){
            sum+=treee[2*u];
            return;
        }
        travel(2*u+1,v);
        if(flag){
            sum+=treee[2*u+1];
            return;
        }
    }
    
    int main(){
        int q; cin >> q;
        while(q--){
            int x,u,v,w;; cin >> x;
            if(x==1){
                cin >> u >> v >> w;
                int father=find_public_father(u,v); 
                // cout << "their father is:" << father << endl;
                flag=0; add(father,u,w);
                flag=0; add(father,v,w);
            }else if(x==2){
                cin >> u >> v;
                int father=find_public_father(u,v);
                sum=0;
                flag=0; travel(father,u);
                flag=0; travel(father,v);
                cout << sum << endl;
            }
            // for(int i=0;i<8;i++){
            //     cout << treee[i] << " ";
            // }
        }
        // system("pause");
        return 0;
    }
    

    正解:https://www.cnblogs.com/wzl19981116/p/10087302.html

    void Add(ll x,ll y,ll w)
    {
        while(1)
        {
            if(x>y)
            {
                a[x]+=w;
                x/=2;
            }else if(x<y)
            {
                a[y]+=w;
                y/=2;
            }else
                break;
        }
    }
    ll query(ll x,ll y)
    {
        ll ans=0;
        while(1)
        {
            if(x>y)
            {
                ans+=a[x];
                x/=2;
            }else if(x<y)
            {
                ans+=a[y];
                y/=2;
            }else
            {
                return ans;
            }
        }
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 11月3日
  • 已采纳回答 10月26日
  • 创建了问题 10月22日

悬赏问题

  • ¥15 nslt的可用模型,或者其他可以进行推理的现有模型
  • ¥15 arduino上连sim900a实现连接mqtt服务器
  • ¥15 vncviewer7.0安装后如何正确注册License许可证,激活使用
  • ¥15 phython如何实现以下功能?查找同一用户名的消费金额合并2
  • ¥66 关于人体营养与饮食规划的线性规划模型
  • ¥15 基于深度学习的快递面单识别系统
  • ¥15 Multisim仿真设计地铁到站提醒电路
  • ¥15 怎么用一个500W电源给5台60W的电脑供电
  • ¥15 请推荐一个轻量级规则引擎,配合流程引擎使用,规则引擎负责判断出符合规则的流程引擎模板id
  • ¥15 Excel表只有年月怎么计算年龄