「网络流 24 题」数字梯形

「网络流 24 题」数字梯形
问题一:从源点向最上面的每个点连权值为0,容量为1的边,然后将每个点i拆成Xi和Yi,并且从Xi向Yi连接容量为1,权值为为-d的边,然后从最下面的边向汇点连接权值为1,容量为1的边。这种方法可以保证每个点每条边都只被经过一次
问题二:问题一从将每个点拆成Xi和Yi以并且连接容量为1的边,以保证每个点只被经过一次。所以对于问题二只要重新建图,然后不再拆点

Last modification:October 25th, 2018 at 02:13 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment