首页 > 代码库 > [bzoj 1064][NOI2008]假面舞会(dfs判断环)
[bzoj 1064][NOI2008]假面舞会(dfs判断环)
题目:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1064
分析:
如果a看到b,则a->b
那么:
1、如果图中有环,则说明这个环的长度肯定是答案的倍数。所以最大种类数=所有环的长度的gcd,最小种类数=所有环的长度的公约数中>=3的最小数
2、如果图中没有环且都是单独的长链,那么最大种类数=每个联通图中最长链的和,最小种类数=3(如果没有则-1)
3、要考虑一种特殊情况:a->b->c->d a->e->d,这样的图确实没有环,但是不能按长链做,仔细分析会发现这种情况两天链的差是答案的倍数,所以可以归结到1中一起求gcd
有一个简单的实现方法:
对于每个联通图:对建单向边的同时,建一个权值为-1的反边。任取一个点标为0,向下dfs,每次点的号码+1,如果我们遇到了某个点以前标过,那么就说明遇到了环,环的长度=|我们想要给这个点标的数-这个点已经标的数|,并且不修改这个点的标号。这样可以巧妙的把1、3结合到一起,对于第3个情况,找出来的正好是差值。
[bzoj 1064][NOI2008]假面舞会(dfs判断环)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。