likeJ

拓扑排序

# Hash 和 Hash 表(1) # kmp 算法(1) # LCA（最近公共祖先）(1) # 二分(2) # 广搜bfs(16) # 树形dp(3) # 深搜dfs(8) # 贪心(4) # 递推(6) 1024程序员节(1) c++杂题(3) hash(4) STL(1) ST表(1) 二分图(5) 信息奥赛一本通——高效进阶(13) 动规dp(17) 单调栈(6) 单调队列(8) 图论(1) 并查集(9) 快速幂(2) 数论(2) 最小生成树(3) 最短路径(15) 未归档(4) 树状数组(4) 状态压缩(7) 矩阵乘法(2) 离散化(4) 线段树(5) 赛后分析(88) 邻接表(2)

/ 注册

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

P1137 旅行计划（拓扑排序）

旅行计划题目传送门解题思路这题就是拓扑排序+dp 先拓扑排序找相连的点再用dp统计答案拓扑排序 AC代码 #include<iostream> using namespace std; int n,m,x,y,h,t,num,tot,b[100005],c[1000...

2021-03-26

0 362

奖金（拓扑排序）

奖金 Description 由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。　　于是Mr.Z下令召开m方会谈。每位参加会谈的代表提出了自己的意见：“我认为...

2021-03-26

0 715

工程（拓扑排序）

工程 Description 张三是某工程公司的项目工程师。一天公司接下一项大型工程，该公司在大型工程的施工前，先要把整个工程划分为若干个子工程，并把这些子工程编号为1、2、…、N；这样划分之后，子工程之间就会有一些依赖关系，即一些子工程必须在某些子工程完成之后才能施工，公司需要工程师张三计算整...

2021-03-26

0 434

P4017 最大食物链计数（拓扑排序）

P4017 最大食物链计数题目传送门解题思路这题就是拓扑排序拓扑排序的精髓就在于每个点只会入队一次，每条边只会通过一次，所以时间复杂度就有很好的保证，O(N+M)，SPFA的玄学时间复杂度）。正确性说明：题目的补充说明告诉我们这是一张DAG（有向无环图），因此必定存在一个入度为0的...

2021-03-26

0 429

P1983 车站分级（拓扑排序）

车站分级题目传送门解题思路这题就是用拓扑排序分层首先是建图每进行一次输入，就将没有停靠的站与停靠的站都建立一条边因为题目样例不怎么大，所以可以用邻接矩阵 for(int i=1;i<=m;i++)//输入 { cin>>x; memset(c,0,s...

2021-03-26

0 626

P1347 排序（拓扑排序）

排序题目传送门解题思路这题虽然是一道蓝题，但他的数据很小，所以，我们可以每输入一个关系就拓扑一次我们可以把结果分为三种情况 1.根据前x个关系得到整体关系这里我们可以用拓扑把度清零，记录每个字母都出现过并且判断最长的链是多少就行了即f[a[i].to]=max(f[a[i]....

2021-03-26

0 573