[POJ 3592] 强连同分量、拓扑排序、动态规划

【题目大意】给定一个N*M得矩阵,#表示不可以走,0..9表示走到这上面可以得到的分数(每个点只能采集一次)一开始你在左上角,只能向下走或向右走。然后有一些地方有传送门,可以选择无耗损地从这一点传到目标点,也可以选择不传,问最多能得到多少分。

【算法分析】先缩点,然后拓扑排序,最后用dp求最长路,输出就行了。

【其它】悲剧,RE了N遍,不过又MS并非RE得问题,我一开始把不能走到的点也算到DP序列里去了,居然一直RE。。。搞不懂为什么。改了以后终于AC。

【CODE】

#include

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注