YbtOJ 594「费用流」大图书馆

(Updated: )
oi

题目链接：YbtOJ #594

小 A 新开了一个大图书馆（初始里面没有书）。

书的类型有 $n$ 种，其中第 $i$ 种书的价格为 $c_i$。小 A 可以在任意时刻买书。

同学们经常来图书馆借书，每天上午会来借走恰好一本书，且第 $i$ 天需要的书目类型为 $a_i$（不同天的 $a_i$ 可能会相同）。由于同学们看书速度飞快，当天傍晚即可把书返还给图书馆。

为了满足同学们的需求，当同学来借书时，必须满足 TA 所想要类型的书目存在。

然而图书馆内最多只能装 $k$ 本书，若存书数量超过了 $k$，小 A 就不得不选择一些多余的书扔掉。当一种类型的书扔掉后，想要再借出就需要重新购买。

求小 A 至少需要花费多少钱，才能满足同学们的所有需求。

$1\leq n,k\leq 1000$，$1\leq a_i\leq n$，$0\leq c_i\leq 10^6$。

Solution

强制每天都买书，每天都需要提交书。不存到下次使用的书直接当场提交了，要存到下次使用的书可以存下来在下次强制购买之前回头提交。

为了消去存下来再次使用的书的强制购买费用，考虑定义一个“卖书”操作，即如果在强制购买之前手上已经有需要的书了，可以把手上这本卖了。具体地，将花费减去 $c_i$，并将这本书提交到上一次需要这本书的那天。

因此，把每天拆成 $u_0$ 和 $u_1$，用 $u_0$ 表示上午，用 $u_1$ 表示傍晚，然后连下列几类边：

从超级源向 $u_0$ 连一条容量为 $1$，花费为 $c_{a_u}$ 的边，表示强制每天买书。

从 $u_1$ 向超级汇连一条容量为 $1$，花费为 $0$ 的边，表示强制每天都需要提交书。

从 $u_0$ 向 $u_1$ 连一条容量为 $1$，花费为 $0$ 的边，表示不存书，直接提交。

从 $u_0$ 向 $(u+1)_0$ 连一条容量为 $k-1$，花费为 $0$ 的边，表示有 $k-1$ 个位置可以用于存书（减去的 $1$ 是留给下一天的书的位置）。

从 $(u-1)0$ 向 $pre[a_u]_1$ 连一条容量为 $1$，花费为 $-c{a_u}$ 表示卖书（$pre[x]$ 表示上次需要第 $x$ 种书的位置）。

这样建图的点数和边数都是 $O(n)$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=1010,M=N<<1,E=N*10;
int n,k,a[N],c[N],v[N],Ans,Cost,fir[M],nxt[E],son[E],w[E],cost[E],tot=1,C[M],F[M],P[M],vis[M],S,T,inf;
I void Add(CI x,CI y,CI z,CI c){nxt[++tot]=fir[x],fir[x]=tot,son[tot]=y,w[tot]=z,cost[tot]=c,nxt[++tot]=fir[y],fir[y]=tot,son[tot]=x,w[tot]=0,cost[tot]=-c;}
#define to son[i]
deque<int> q;
#define to son[i]
I bool Spfa(){//寻找增广路
    RI u,i;W(!q.empty()) q.pop_front();q.push_front(S);memset(C,63,sizeof(C)),memset(vis,0,sizeof(vis));F[S]=inf=C[0];C[S]=0;W(!q.empty())
        for(i=fir[vis[u=q.front()]=0,u],q.pop_front();i;i=nxt[i]) if(w[i]>0&&C[to]>C[u]+cost[i]) C[to]=C[u]+cost[P[to]=i],F[to]=min(F[u],w[i]),!vis[to]&&(q.empty()?q.push_front(to),0:(C[to]>C[q.front()]?q.push_back(to):q.push_front(to),0),vis[to]=1);
    return C[T]<inf;
}
I void MCMF(){//最小费用最大流
    RI i;W(Spfa()){
        for(i=T;i^S;i=son[P[i]^1]) w[P[i]]-=F[T],w[P[i]^1]+=F[T];
        Ans+=F[T],Cost+=C[T]*F[T];
    }return ;
}
int main(){
    freopen("bibliotheca.in","r",stdin),freopen("bibliotheca.out","w",stdout);
    RI i;for(read(n,k),i=1;i<=n;i++) read(a[i]);for(i=1;i<=n;i++) read(c[i]);
    for(S=0,T=n<<11,i=1;i<=n;i++) Add(S,i,1,c[a[i]]),Add(i,i+n,1,0),Add(i+n,T,1,0),i^n&&(Add(i,i+1,k-1,0),0),v[a[i]]&&(Add(i-1,v[a[i]]+n,1,-c[a[i]]),0),v[a[i]]=i;//建图，具体含义见题解
    return MCMF(),writeln(Cost),0;
}