首页 > 代码库 > [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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。