icontofig | 发布于 2019-07-03 02:49:37 | 阅读量 101 | 最短路 分层图
发布于 2019-07-03 02:49:37 | 最短路 分层图
洛谷P1073 最优贸易 分层图SPFA
题解这题其实有好几种做法,听说还有tarjan缩点+topsort+dp的做法,不过想了想真的是太恶心了…… 于是换一种想法,我们可以像最小费用最大流惯用套路一样,进行拆点,把一个点的不同状态转化成不同的点。 因为只能买卖一次,这道题其实可以分作三种状态: 1.没有买入也没有卖出 2.买入了但是没卖出3.买入了并且卖出了。 按照三种方案来拆点,每个点拆成三个,于是可以把点分成这三层。 可以将每层内的点的距离认为是0距离,表示不买入也不卖出。每个点与自己下一层的对应点连有向边,表示买入或者卖出。 分成两种情况: 1.买入,第一层向第二层对应点连边,边权为当前城市水晶球价格的负值,代表花钱买入。
继续阅读