[POJ 3592] 强连同分量、拓扑排序、动态规划 发布者:edward_mj 14 1 月, 2010 于[POJ 3592] 强连同分量、拓扑排序、动态规划留下评论 【题目大意】给定一个N*M得矩阵,#表示不可以走,0..9表示走到这上面可以得到的分数(每个点只能采集一次)一开始你在左上角,只能向下走或向右走。然后有一些地方有传送门,可以选择无耗损地从这一点传到目标点,也可以选择不传,问最多能得到多少分。 【算法分析】先缩点,然后拓扑排序,最后用dp求最长路,输出就行了。 【其它】悲剧,RE了N遍,不过又MS并非RE得问题,我一开始把不能走到的点也算到DP序列里去了,居然一直RE。。。搞不懂为什么。改了以后终于AC。 【CODE】 #include