把梯形中每一个位置抽象为两个点(i.a)(i.b),建立附加源S汇T.
1,对每一个点i从(i.a)到(i.b)连接1条容量为1,费用为点i权值的有向边.
2,从S向梯形顶层每一个(i.a)连1条容量为1,费用为0的有向边.
3,从梯形底层每一个(i.b)向T连1条容量为1,费用为0的有向边.
4,对每一个点i和下面的两个点j,分别连1条从(i.b)到(j.a)容量为1,费用为0的有向边.
求最大费用最大流,费用流值就是结果.
把梯形中每一个位置看作1个点i,建立附加源S汇T.
1,从S向梯形顶层每一个i连1条容量为1,费用为0的有向边.
2,从梯形底层每一个i向T连1条容量为无穷大,费用为0的有向边.
3,对每一个点i和下面的两个点j,分别连1条从i到j容量为1,费用为点i权值的有向边.
3,对每一个点i和下面的两个点j,分别连1条从i到j容量为无穷大,费用为点i权值的有向边.
首先求出所有仓库存货量平均值,设第i个仓库的盈余量为A[i],A[i] = 第i个仓库原有存货量 - 平均存货量.建立2分图,把每一个仓库抽象为两个节点Xi和Yi.增设附加源S汇T.
1,如果A[i]>0,从S向Xi连1条容量为A[i],费用为0的有向边.
2,如果A[i]<0,从Yi向T连1条容量为-A[i],费用为0的有向边.
3,每一个Xi向两个相邻顶点j,从Xi到Xj连接1条容量为无穷大,费用为1的有向边,从Xi到Yj连接1条容量为无穷大,费用为1的有向边.
求最小费用最大流,最小费用流值就是最少搬运量.