简要介绍一下如何构图
拆点:因为每个方格只取一次,但要走两遍,因此我们考虑对于矩阵中每个方格拆为两个节点,一个为流入点,记为 iii ;一个为流出 点,记为 iii '。连两条边从 i−>ii->ii−>i ’,两条容量都为 111 ,费用为 −g-g−g [ iii ][ jjj ]和 000 。
编号:这个大家有各自的习惯。我的题解中具体看我程序中的 hashinhashinhashin 和 hashouthashouthashout 函数和注释, hashinhashinhashin 用于编号我前文所提到 的 iii , hashouthashouthashout 用于编号我前文所提到的 iii '。
连接节点:每个节点的 outoutout 连接它的右边和它下边节点的流入点,对于边界特殊处理一下, sss 连( 000 , 000 )的入点,( n−1n-1n−1 , n−1n-1n−1 )连 ttt 点。
这样构图跑一遍 spfaspfaspfa 的最小费用最大流就 OKOKOK 了。