夢に僕らで帆を張って
来るべき日のために夜を超え

标签 拓扑排序 下的文章

October 31, 2019

洛谷P1983 车站分级

题意略数据范围:$1 \le n,m \le 1000$题解由题意“则始发站、终点站之间所有级别大于等于火车站$x$的都必须停靠”可知未停靠的站级别一定比$x$的级别小将大小关系转化为图:将车站视为点,由级别小的车站向级别大的车站连边随后从入度为$0$的点入手,用拓扑排序求出答案代码:#include<iostream> #include<cstdio> #inclu...
October 18, 2019

洛谷P4099/HEOI2013 SAO

题意给出一个连成树的有向图,求拓扑序数量数据范围:$1 \le n \le 1000$题解树形$dp$,用$f[i][j]$表示以$i$为根的子树中,节点$i$的排名为$j$的方案数考虑转移,对于$u$为$v$的父节点,$x$在原序列中排名为$p_1$,新序列中排名为$p_3$;$y$在原序列中排名为$p_2$,新序列中排名为$p_4$,从$f[u][p_1]$与$f[v][p_2]$转移到...