louhc

分类

未归档(78) 题解(81)

/ 注册

全部文章（共3篇）

题解 | 算法竞赛进阶指南圆桌骑士

思路先建反图,也就是说,没有憎恨关系的骑士之间连边,这样问题就变成了求有多少个骑士不在任何一个奇环中.很明显一个奇环的所有点都在同一个v-DCC(点双连通分量)中,因此先tarjan找出所有v-DCC.如果一个v-DCC中有一个奇环,那么该v-DCC所有点都在某一个奇环上.为什么呢?假设有一个奇环...

tarjan 缩点

2019-08-31

0 786

题解 | 算法竞赛进阶指南学校网络

思路因为对于一个环,给其中任何一点支援都是等效的,因此先对原图进行缩点.对于缩点后的图,入度为0的点不能被其他学校支援,其他入读不为0的都能被其他学校支援,因此第一问答案就是入度为0的点.而要满足第二问的条件,必须使都在一个强连通分量才行.这样答案就是max(入度为0的点个数,出度为0的点个数)....

tarjan 缩点

2019-08-26

1 531

题解 | 算法竞赛进阶指南银河

思路按照题意建边,若亮度大于等于的,连有向边,大于则为,相等则为.然后缩点,如果出现一个强连通子图内有大于0的边,说明存在正环,无解.然后拓扑排序,若有边,,直接DAG上DP即可.当然你想跑差分约束我也没办法qwq. 代码话说那时候脑子抽了还是怎么样,本地运行爆栈了,我还以为一定要手工栈什么的q...

tarjan 缩点

2019-08-24

0 551