【题目】
CF
你有一个容量为 k k k的空书架，现在共有 n n n个请求，每个请求给定一本书 a i a_i ai?，如果你的书架里没有这本书，你就必须以 w i w_i wi?的价格购买这本书放入书架。当然，你可以在任何时候丢掉书架里的某本书。请求出完成这 n n n个请求所需要的最少价钱。
n , k ≤ 80 , w i ≤ 1 0 6 n,k\leq 80,w_i\leq 10^6 n,k≤80,wi?≤106
【解题思路】
范围很小可以考虑网络流，有价格限制即考虑费用流。
对于第 i i i天，我们先强制要买一本书，那么连边 ( S , i , 1 , w a i ) (S,i,1,w_{a_i}) (S,i,1,wai??)。由于一本书如果必须要丢，那么在什么时候丢都一样，于是接下来新建一排中转点来表示这天的物品丢不丢，那么连边 ( i , i + n , 1 , 0 ) (i,i+n,1,0) (i,i+n,1,0)，表示这个物品不保留。还需要连 ( i + n , T , 1 , 0 ) (i+n,T,1,0) (i+n,T,1,0)表示只能丢一次。为满足至多保留 k ? 1 k-1 k?1本书的限制还要连 ( i , i + 1 , k ? 1 , 0 ) (i,i+1,k-1,0) (i,i+1,k?1,0)。
对于一本书，若它之前已经在书架上，那么我们可以不买入，也可以看作卖出再买入，那么我们可以连 ( i ? 1 , p r e a i + n , 1 , ? w a i ) (i-1,pre_{a_i}+n,1,-w_{a_i}) (i?1,preai??+n,1,?wai??)，表示在前一天卖出，同时会占用它到 T T T的边。
跑最小费用最大流即可。
【【费用流】CF802C Heidi and Library (hard)】复杂度 O ( c o s t f l o w ( n 2 , n 2 ) ) O(costflow(n^2,n^2)) O(costflow(n2,n2))
【参考代码】
#include
using namespace std;
const int N=165,M=N*6,inf=0x3f3f3f3f;
int n,K,tot,S,T,ans;
int head[N],dis[N],inq[N],a[N],w[N],pre[N],ins[N];
queueq;
struct Tway{int v,nex,w,c;
}e[M];
void add(int u,int v,int w,int c)
{
e[++tot]=(Tway){v,head[u],w,c};
head[u]=tot;
e[++tot]=(Tway){u,head[v],0,-c};
head[v]=tot;
}int read()
{
int ret=0;
char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) ret=ret*10+(c^48),c=getchar();
return ret;
}bool spfa()
{
memset(dis,0x3f,(T+2)<<2);
q.push(S);
dis[S]=0;
inq[S]=1;
while(!q.empty())
{
int x=q.front();
q.pop();
inq[x]=0;
for(int i=head[x];
i;
i=e[i].nex)
{
int v=e[i].v;
if(e[i].w && dis[v]>dis[x]+e[i].c)
{
dis[v]=dis[x]+e[i].c;
if(!inq[v]) q.push(v),inq[v]=1;
}
}
}
return dis[T]<(inf/2);
}int dfs(int x,int flow)
{
if(x==T || !flow) return flow;
int u,used=0;
ins[x]=1;
for(int i=head[x];
i;
i=e[i].nex)
{
int v=e[i].v;
if(ins[v] || !e[i].w || (dis[v]!=dis[x]+e[i].c)) continue;
u=dfs(v,min(e[i].w,flow-used));
e[i].w-=u;
e[i^1].w+=u;
used+=u;
ans+=e[i].c*u;
}
ins[x]=0;
return used;
}int main()
{
#ifdef Durant_Lee
freopen("CF802C.in","r",stdin);
freopen("CF802C.out","w",stdout);
#endif
n=read();
K=read();
S=2*n+1;
T=S+1;
tot=1;
for(int i=1;
i<=n;
++i) a[i]=read();
for(int i=1;
i<=n;
++i) w[i]=read();
for(int i=1;
i<=n;
++i)
{
add(S,i,1,w[a[i]]);
add(i+n,T,1,0);
add(i,i+n,1,0);
if(i 
