Reincarnation

正因为梦易碎，才格外美好。

UTPC2011H - キャッシュ战略

发表于 更新于 分类于
本文字数： 3.9k 阅读时长 ≈ 4 分钟

上古毒瘤网络流题。

题目简介

题目名称：现金战略
题目来源：

评测链接：https://atcoder.jp/contests/utpc2011/tasks/utpc2011_8

形式化题意：有 个盒子和 个小球，一共 次操作 ，表示将第 个小球放入盒子中，并产生 的代价。如果盒子满了，就必须从某一个盒子中拿出另一个小球并放入 ，总之，必须保证操作 执行结束后，盒子中至少存在 个 小球。

数据范围：

不容易发现这是一道费用流。

正向思考是一个艰难的问题，所以我们假定所有的球都需要被替换（产生代价），然后通过负费用算出最多能省多少。

如果对于一个小球 ，我们要求其保留至下一次放入，就可以节省 的代价，但是在 操作内就会消耗一个盒子。这种方式我们在同一时间一共可以做 这样的操作，也就是在同一个时间节省 种代价。

考虑 ，但是具有后效性，反向 肯定也不行。贪心就更不用想了。

以盒子数为流量，代价为费用建立费用流。

我们钦定每一次都会产生代价，也就是每一次都要放进去。但我们有 次机会可以使当前操作不产生代价，但在同一时刻也只有 次。而如果我们让某一次操作不产生代价，就会在 内占用一个盒子。其中 表示第 个小球上一次放入的时间。

所以，对于每一次操作，我们有 种选择：

  1. 放入，并产生 的代价；
  2. 从上一次放入后就不移动，并让其延续到当前操作，不产生代价。

容易发现，第 个选择实际上就是要求我们在 内不执行第 个选择。

所以我们考虑按以下方式建图：

  • 建立 的操作结点，以及源汇点 ；
  • 从 到 连边，流量 ，费用 ；
  • 从 到 连边，流量 ，费用 ；
  • 从 到 连边，流量 ，费用 ；
  • 从 到 连边，流量 ，费用 。

答案是 ，其中 表示最小费用。

因为对于每一个时刻，我们都至少要留出一个盒子给当前操作的小球，所以我们能够维护保持的小球至多有 个，总流量为 。而至于为什么是从 ，如果这个小球在下一次放入前被拿出来了，那无论是在 被拿出对结果的影响是一样的，我们都必须要再次放入，所以我们钦定在 内不被拿出，就会产生 的代价。而在 时，我们是必须会执行第一个选择的。

附上官方题解。以及感谢与我一同探究的 。

最后整几个注意事项：

  • 上古题，记得答案最后换行。
  • 不建议开 long long，好像会超时，这个数据范围 int 是可以过的。
  • 请注意，如果存在 的情况，就会使得图中出现一个负环，然后要么答案会变小，要么会死循环。所以我们在建图之前要进行一次去重处理，把所有 的情况剔除掉。
AC 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
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
92
93
94
95
96
97
98
99
100
101
102
103
// ----- Eternally question-----
// Problem: H - キャッシュ戦略
// Contest: AtCoder - UTPC 2011
// URL: https://atcoder.jp/contests/utpc2011/tasks/utpc2011_8
// Memory Limit: 292 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-03-16 14:37:28
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
const int MAXM=12,MAXN=1e4+10,MAXK=1e4+10,MAXV=1e4+10,MAXE=1e5+10;
const int INF=0x3f3f3f3f;
int M,N,K,S,T;
int Wgt[MAXN];
struct Net
{ int next,to,val,cost; }Edge[MAXE<<1];
int Head[MAXV],Cur[MAXV],Total=1;
inline void addEdge(int u,int v,int w,int c)
{
    Edge[++Total]=(Net){Head[u],v,w,c};Head[u]=Total;
    Edge[++Total]=(Net){Head[v],u,0,-c};Head[v]=Total;
}
int Dist[MAXV],ret;
bool Vis[MAXV];
inline bool Spfa(int s,int t)
{
	for(int i=S;i<=T;++i) Dist[i]=INF;
	for(int i=S;i<=T;++i) Cur[i]=Head[i];
    std::queue<int>Q;
    Q.push(s),Dist[s]=0,Vis[s]=1;
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        Vis[u]=0;
        for(int e=Head[u];e;e=Edge[e].next)
        {
            int v=Edge[e].to;
            if(Edge[e].val&&Dist[v]>Dist[u]+Edge[e].cost)
            {
                Dist[v]=Dist[u]+Edge[e].cost;
            	if(!Vis[v]) Q.push(v),Vis[v]=1;
            }
        }
    }
    return Dist[t]!=INF;
}
int Dfs(int x,int inf)
{
    if(x==T) return inf;
    Vis[x]=1;
    int flow=0;
    for(int e=Cur[x],v;e&&flow<inf;e=Edge[e].next)
    {
        Cur[x]=e,v=Edge[e].to;
        if(!Vis[v]&&Edge[e].val&&Dist[v]==Dist[x]+Edge[e].cost)
        {
            int k=Dfs(v,std::min(Edge[e].val,inf-flow));
            if(k)
            {
                ret+=k*Edge[e].cost;
                Edge[e].val-=k,Edge[e^1].val+=k,flow+=k;
            }
        }
    }
    Vis[x]=0;
    return flow;
}
inline int SSP()
{
    int res=0,flow;
    while(Spfa(S,T)) while(flow=Dfs(S,INF)) res+=flow;
    return res;
}
int Sum,Lst[MAXN],Id[MAXN],Idx;
signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	scanf("%d%d%d",&M,&N,&K);S=0;
	for(int i=1;i<=N;++i) scanf("%d",&Wgt[i]);
	std::memset(Lst,-1,sizeof(Lst));
	for(int i=1,x;i<=K;++i)
	{
		scanf("%d",&x);
		if(Id[Idx]!=x) Id[++Idx]=x;
	}
	K=Idx,T=Idx+1;
	for(int i=1;i<=K;++i)
	{
		if(~Lst[Id[i]]) addEdge(Lst[Id[i]]+1,i,1,-Wgt[Id[i]]);
		Lst[Id[i]]=i,Sum+=Wgt[Id[i]];
	}
	addEdge(S,1,M-1,0);
	for(int i=1;i<=K;++i) addEdge(i,i+1,INF,0);
	SSP();
	printf("%d\n",Sum+ret);
	return 0;
}
/*

*/
相关文章