将每天拆成两个点,i点用于接收干净餐巾,i'点用于接收脏餐巾,那么: ·从i向T连流量为Ri,费用为0的边,如果满流则表示当天的餐巾数量足够 ·从S向i'连流量为Ri,费用为0的边,表示每天结束时接收到Ri块脏餐巾 ·从S向i连流量为∞,费用为p的边,表示每天开始时购买餐巾 ·从i'向i+m连流量为∞,费用为f的边,表示送快洗 ·从i'向i+n连流量为∞,费用为s的边,表示送慢洗 ·从i'向(i+1)'连流量为∞,费用为0的边,表示将脏餐巾留到下一天 之后求最小费用最大流即可
题目461 [网络流24题] 餐巾
AAAAAAAAAAAA
5
评论
2024-03-16 17:14:14
|