YbtOJ 594「费用流」大图书馆
YbtOJ 594「费用流」大图书馆
题目链接：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
#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;
}腾讯云开发者
