OI - Heidi and Library Hard(Codeforces) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - Heidi and Library Hard(Codeforces)

发表于 分类于 Valine：

还是没搞懂正睿怎么就把这道题转换成 k 覆盖问题的

# 题面

点击展开/折叠题面

有 $n$ 本书编号为 $1\sim n$。

你有一个可以放 $m$ 本书的书架。你可以随时以 $c_i$ 的价格购买第 $i$ 本书放入书架，也可以丢弃书架中的书（丢掉了就没了）。任意时刻书架中的书的数量不超过 $m$。

在接下来的 $n$ 天中，你希望第 $i$ 天时，书架中有第 $a_i$ 本书。

求最小花费。

# 解析

首先这是一道网络流题，既然要求最小花费当然是费用流。

一定存在一种合法的方案，即每一天都买第 $a_i$ 本书，然后把它丢掉。我们需要找到哪些购买是“多余”的。

假设第 $i,j$（$i< j$） 天都购买了书 $x$，我们可以通过第 $i$ 天购买后放入书架、一直到第 $j$ 天再丢弃来实现“减免”第 $j$ 天的代价。

但是这样不好建图，换一种理解方式：仍然每一天都要买书，但是新增一种“卖书”操作。我们可以在第 $i$ 天购买书 $x$ 后放入书架，直到第 $j-1$ 天卖掉（代价减免 $c_x$）。

> Tab. $(a,b)$ 表示一条容量为 $a$，代价为 $b$ 的边。

于是可以这样建图：

  • 对于 $n$ 天，每天建两个点 $v_i,v_i’$；
  • $S$ 向 $v_i$ 连边 $(1,c_{a_i})$，表示第 $i$ 天购买；
  • $v_i$ 向 $v_i’$ 连边 $(1,0)$，表示第 $i$ 天购买后直接丢弃；
  • $v_i’$ 向 $T$ 连边 $(1,0)$，表示第 $i$ 天买的这本书没了；
  • $v_i$ 向 $v_{i+1}$ 连边 $(m-1,0)$，表示第 $i$ 天（以及之前买的书）存在书架里，因为每天买书会首先放入书架，所以书架的实际容量只有 $m-1$，此时该边的流量就是储存在书架中的书的数量；
  • 设 $p_i$ 表示上一次购买书 $a_i$ 是哪一天，$v_{i-1}$ 向 $v_{p_i}’$ 连边 $(1,-c_{a_i})$，表示第 $i-1$ 天卖掉这本书（流向 $v_{p_i}’$ 后，就会流向 $T$，然后这本书就没了）。

点数 $2n$，边数 $5n$，Dinic+SPFA 完全跑得过。

# 源代码

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/*Lucky_Glass*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef pair<int,int> pii;
const int N=100,INF=1e9+7;
pii operator +(pii a,pii b){return make_pair(a.first+b.first,a.second+b.second);}

struct GRAPH{
	int head[N<<1],nxt[N*10],to[N*10],cap[N*10],cst[N*10],ncnt;
	GRAPH(){ncnt=1;}
	void AddEdge(int u,int v,int ca,int cs){
		int p=++ncnt,q=++ncnt;
		nxt[p]=head[u],to[p]=v,cap[p]=ca,cst[p]=cs,head[u]=p;
		nxt[q]=head[v],to[q]=u,cap[q]=0,cst[q]=-cs,head[v]=q;
	}
	int operator [](const int &u){return head[u];}
}Gr;

int n,m,S,T;
int val[N],bok[N],las[N],dis[N<<1],head[N<<1];
bool inq[N<<1],vis[N<<1];

inline int Ri(){
	register int r=0,c=getchar();
	while(c<'0' || '9'<c) c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+c-'0',c=getchar();
	return r;
}
queue<int> que;
bool SPFA(){
	for(int i=1;i<=T;i++) head[i]=Gr[i],dis[i]=INF;
	que.push(S);dis[S]=0,inq[S]=true;
	while(!que.empty()){
		int u=que.front();que.pop();
		inq[u]=false;
		for(int it=Gr[u];it;it=Gr.nxt[it]){
			int v=Gr.to[it];
			if(Gr.cap[it]<=0 || dis[v]<=dis[u]+Gr.cst[it]) continue;
			dis[v]=dis[u]+Gr.cst[it];
			if(!inq[v]) inq[v]=true,que.push(v);
		}
	}
	return dis[T]!=INF;
}
pii Aug(int u,int in){
	if(u==T) return make_pair(in,0);
	pii res(0,0);
	vis[u]=true;
	for(int &it=head[u];it;it=Gr.nxt[it]){
		int v=Gr.to[it];
		if(vis[v] || Gr.cap[it]<=0 || dis[v]!=dis[u]+Gr.cst[it]) continue;
		pii tov=Aug(v,min(in-res.first,Gr.cap[it]));
		res=res+tov;res.second+=tov.first*Gr.cst[it];
		Gr.cap[it]-=tov.first,Gr.cap[it^1]+=tov.first;
		if(res.first==in) break;
	}
	vis[u]=false;
	return res;
}
pii Dinic(){
	pii res(0,0);
	while(SPFA()){
		pii now=Aug(S,INF);
		res=res+now;
	}
	return res;
}
int main(){
	n=Ri(),m=Ri();
	for(int i=1;i<=n;i++) bok[i]=Ri();
	for(int i=1;i<=n;i++) val[i]=Ri();
	S=2*n+1,T=S+1;
	for(int i=1;i<=n;i++){
		Gr.AddEdge(S,i,1,val[bok[i]]);
		Gr.AddEdge(i,i+n,1,0);
		Gr.AddEdge(i+n,T,1,0);
		if(i<n) Gr.AddEdge(i,i+1,m-1,0);
	}
	for(int i=1;i<=n;i++){
		if(las[bok[i]]) Gr.AddEdge(i-1,las[bok[i]]+n,1,-val[bok[i]]);
		las[bok[i]]=i;
	}
//	return 0;
	printf("%d\n",Dinic().second);
	return 0;
}

THE END

Thanks for reading!

> Linked 瀘沽寻梦-网易云