superlevin 2022-05-12 12:58 采纳率: 100%
浏览 58
已结题

DAG演算法透過C++實踐

Here is a Directed Acyclic Graph (DAG) with weight on nodes.

If there is a directed path from node to node , node is a successor of node . itself is defined as one of the successors of as well.
Please calculate the maximal weight among weights of all successors of for each in the DAG.

The first line is n,m , which are number of nodes and directed edges in the DAG.
The following n line are n integers representing weight of node , i0≤i<.
The following m line after weights are m pair of integers(a,b) , which represents directed edge from a to b .
Constraints
0<n<=10000
0<m<=50000
0<wieght<=10000
0<=a,b<n
Output Format
Print n integers in a line separate with a space.

The i-th integer is the answer corresponding to node i 0<=i<n
Sample Input
4 4
1 4 3 2
0 1
1 2
1 3
3 2
Sample Output
4 4 3 3
Sample Input
5 5
1 4 3 2 8
0 1
1 2
1 3
3 2
0 4
Sample Output
8 4 3 3 8

請問如何解?


#include <cstdio> 
#include <vector> 
#include <iostream>
 #include <algorithm> 
using namespace std;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
return 0;
}

展开全部

  • 写回答

1条回答 默认 最新

  • 丨秋水丨 2022-05-12 13:54
    关注

    img

    #include <cstdio> 
    #include <vector> 
    #include <iostream>
    #include <algorithm> 
    using namespace std;
    struct Node
    {
        int weight;
        std::vector<int> successors;
    };
    int main() {
        int n, m;
        cin >> n >> m;
        std::vector<Node> nodes;
        nodes.resize(n);
        for (int i = 0; i < n; ++i)
        {
            int w;
            cin >> w;
            nodes[i].weight = w;
        }
        for (int i = 0; i < m; ++i)
        {
            int l, r;
            cin >> l >> r;
            nodes[l].successors.push_back(r);
        }
        for (int i = 0; i < n; ++i)
        {
            int maxWeight = nodes[i].weight;
            for (int j = 0; j < nodes[i].successors.size(); ++j)
            {
                if (maxWeight < nodes[nodes[i].successors[j]].weight)
                {
                    maxWeight = nodes[nodes[i].successors[j]].weight;
                }
            }
            cout << maxWeight;
            if (i != n - 1)cout << " ";
        }
        return 0;
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
编辑
预览

报告相同问题?

问题事件

  • 已结题 (查看结题原因) 5月13日
  • 已采纳回答 5月12日
  • 赞助了问题酬金60元 5月12日
  • 创建了问题 5月12日

悬赏问题

  • ¥15 各位专家求此答案解析
  • ¥15 llama-factory训练日志epoch为什么是浮点数?
  • ¥500 我想做一个股票策略的回测AI工具(网页版)python语言、Pine Script
  • ¥15 生信空转NICHES分析中runNICHES函数报错
  • ¥30 地学数据三维可视化基于克里金插值的三维可视化
  • ¥15 stc8g1k08a-sop8控制led代码问题。
  • ¥50 让画布在弹出的新的浏览器页面上运行绘画
  • ¥15 VB6.0获取路径及文件信息问题
  • ¥15 mbed库rsa算法段错误
  • ¥15 SG-cyclic模式Axi-Dma,如何实时更新缓存区内数据