青烟绕指柔

拓扑排序

2-SAT(1) bfs(6) Codeforces(3) dfs(4) Hash(1) HDU(2) KM(1) LCA(2) Link_Cut_Tree(1) LIS(1) Splay(1) STL(7) WQS二分(1) 中等难度(6) 主席树(4) 二分(1) 分块(1) 前缀和(1) 动态规划(15) 博弈论(1) 双连通分量(1) 图论(158) 堆(3) 字符串(5) 差分(1) 并查集(13) 数位dp(3) 数学(1) 数论(12) 无旋treap(2) 最小环(2) 最小生成树(11) 最短路(18) 树形dp(1) 树状数组(16) 树结构(4) 树链剖分(1) 概率dp(2) 相对大小问题(1) 矩阵乘法(3) 离线算法(12) 线性基(2) 线段树(28) 背包问题(2) 莫队(1) 计算几何(8) 贪心(2) 距离表示(1) 题解(4)

/ 注册

全部文章 / 拓扑排序（共4篇）

拓扑排序

很早之前就听说过这个东西，而且自己也尝试着写了一下。然后也就一直没有管过，直到上次做题才发现自己对拓扑排序的理解是多么的浅。什么是拓扑排序呢？对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v...

2019-12-27

0 883

hihoCoder 1175

题目链接小Hi和小Ho所在学校的校园网被黑客入侵并投放了病毒。这事在校内BBS上立刻引起了大家的讨论，当然小Hi和小Ho也参与到了其中。从大家各自了解的情况中，小Hi和小Ho整理得到了以下的信息：校园网主干是由N个节点(编号1…N)组成，这些节点之间有一些单向的网路连接。若存在一条网路连接(...

2019-12-27

0 420

有向无环图

我们可以看出来，我们需要在DAG上面统计有多少到达某个点的路径数。这不就是拓扑排序吗？我们在拓扑排序时，传递a的值，最后计算答案即可、但是减法取模错了，WA了几次。。。。 AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h&...

2019-12-27

0 518

绿豆蛙的归宿

给出一个有向无环的连通图，起点为1，终点为N，每条边都有一个长度。数据保证从起点出发能够到达图中所有的点，图中所有的点也都能够到达终点。绿豆蛙从起点出发，走向终点。到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K 。现在绿...

2019-12-27

0 505