首页 > 代码库 > [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判断环)