【BZOJ1064】【NOI2008】假面舞会

实现方法神奇

把每条边拆成长度为\(1\)的正向边和长度为\(-1\)的反向边,那么这张图中如果出现了环,那么这个环的长度在模答案意义下一定是\(0\),也就是说环长是答案的倍数。那么最大答案就是所有环长度的gcd,最小答案是最大答案的不小于\(3\)的最小约数。

如果没有找到环,那么最大答案就是每个连通块的最长链长度之和,最小答案\(3\)。

说点什么

您将是第一位评论人!

提醒
wpDiscuz