CF802C Heidi and Library (hard) 最小费用流

你有一个容量为k的空书架，现在共有n个请求，每个请求给定一本书ai，如果你的书架里没有这本书，你就必须以ci的价格购买这本书放入书架。

当然，你可以在任何时候丢掉书架里的某本书。请求出完成这n个请求所需要的最少价钱。

做法1:

把每个请求拆成两个点 A,B

A表示买入 B表示卖出

addedge(S,A,1,c[a[i]]) addedge(A,B,1,0) addedge(B,T,1,0) 这样最大流必是n

每天的A向下一天的A连流量为k-1，费用为0的边，表示可以不扔，留到明天，但明天的书还需要一个位置，所以是k-1。

每天的前一天向上一个书?出现的位置的B连一条费用为−c[a[i]]??，流量为1的边，表示在已经有这本书的情况下，可以卖掉这本书

跑一遍最小费用即为答案

做法2:

CF802C Heidi and Library (hard) 最小费用流

原文：https://www.cnblogs.com/Aragaki/p/11731709.html