(QR14)带权的DAG节点排序

2021-04-21 06:29

阅读：461

标签：gre auto back rect 标示 using turn opera rap

带权的DAG节点排序

DAG即Directed Acyclic Graph,有向无环图.用DAG可以描述一些有依赖关系的任务组,而这些任务还有另外一个属性,即都有一个权重,标示这个任务的重要性.
我们需要你来实现一个算法,对DAG里面的节点进行排序,保证排序不违背DAG的依赖关系,即一个任务A如果排在任务B前面,那么在DAG中不能存在由B到A的路径.另外一个要求就是,让权重大的任务尽量优先执行.

输入：在第一行给定DAG的节点数n和边数e.后面n行,每一行是节点的标号和权重, seq weight.最后e行,每一行是对于边的描述, s t.

输出：排序好的节点标号,在一行内输出,空格隔开.

有依赖关系的任务很显然需要拓扑排序，即每次都选择所有依赖任务已经做完的节点，此题每个节点额外有权重，优先选择权重高的即可。由于在拓扑排序中可以使用优先队列来选择度数为0的节点，所以只需要定义一个类，重载其小于号即可。

#include 

using namespace std;

const int N = 1010;

int a[N], degree[N];
vector forword[N];

class Node{
public:
    int id;
    int deg;
    int weight;

    bool operator  o.weight;
    }
};

int main(){
    multiset que;
    int n, e, s, t, seq, w;
    cin >> n >> e;
    for(int i = 1;i > seq >> w;
        a[seq] = w;
        forword[i] = vector();
    }
    for(int i = 1;i > s >> t;
        degree[t]++;
        forword[s].push_back(t);
    }
    for(int i = 1;i

(QR14)带权的DAG节点排序

标签：gre auto back rect 标示 using turn opera rap

原文地址：https://www.cnblogs.com/waitti/p/13282324.html

上一篇：Qt c++5.15 mingw 64位编译 ---ricky.chu

下一篇：Python学习的第二次总结

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：(QR14)带权的DAG节点排序
文章链接：http://soscw.com/essay/77490.html

亲，登录后才可以留言！

(QR14)带权的DAG节点排序

带权的DAG节点排序

评论

热门文章

推荐文章

最新文章

置顶文章