bzoj 1093: [ZJOI2007]最大半连通子图 强联通分量 拓扑排序 DP

这题很容易看出来做法,实现起来也很简单。

首先我们考虑,他这个半联通子图这个概念非常不好处理,我们尝试把他转化一下。想一下,为了求一个最大的半联通子图,显然在一个强联通分量内,我们应该是依次经过某些点,走出一条路径,然后延伸到强联通分量外的路径上。这样子我们可以先求强联通分量,然后在新图上进行DP。相当于找新图的最长路径,(每个是有长度的,为其分量中点的个数)具体DP实现过程伴随拓扑排序,我们对于一个缩点维护dp[i][0]和dp[i][1]分别表示最长路径,和完成这个最长路径的方案数。然后伴随拓扑排序转移一下就可以了。最后统计一下DP数组即可。

发表评论