首页 > 代码库 > [bzoj 1093][ZJOI2007]最大半联通子图(强联通缩点+DP)

[bzoj 1093][ZJOI2007]最大半联通子图(强联通缩点+DP)

题目:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1093

分析:

首先肯定是先把强联通全部缩成一个点,然后成了一个DAG

下面要知道一点:原图的最大半联通子图实际是上是新DAG图的一个最长链

然后就像拓扑排序一样(不过这是以出度为0的点优先,拓扑排序以入度为0的点优先),设f[i]表示以节点i为起始节点的最长链的长度,s[i]表示以节点i为起始节点的最长链的条数,然后就DP一样搞……

注意:

1、缩点的时候有可能有重边,要注意判断

2、在DP的时候s[]求和的时候要一边加一边mod

[bzoj 1093][ZJOI2007]最大半联通子图(强联通缩点+DP)