Gravatar
小金
积分:925
提交:188 / 371

将每天拆成两个点,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      4      评论
2024-03-16 17:14:14