提供一种思路

P2272 [ZJOI2007] 最大半连通子图

__er @ 2023-10-04 22:14:11

tarjan 缩完点不必要拓扑排序,可以倒序 dp,dfs 即可,tarjan 求出来的即为逆拓扑序

不必要建图时判重边,可以对点标记边 dp 时判

码量会小很多

记得判重边判重边判重边


by AKPC @ 2023-10-04 22:15:16

草,我前两个月做的,%%%

可以交题解了(?


by __er @ 2023-10-04 22:17:03

@A_Passing_Creeper 不能吧


by AKPC @ 2023-10-04 22:17:55

@__er emm,,


|