题解 P5470 【[NOI2019]序列】
seajupiter · · 题解
论在看不懂题解的时候如何化悲愤为力量……
本篇题解会尽可能细致具体地解释思路和写法，并顺带提一下我自己调试过程发现的一些代码细节，希望能帮到大家。（希望亲爱的管理员通过一下哈）
算法：贪心模拟费用流
费用流做法
这个题的费用流做法已经有两篇题解都讲到了，最关键的思路点就在于把 “必须至少有
然而很显然时间复杂度过高，你的费用流是不大可能跑过所有数据的。实际上普通的spfa求最短路的MCMF算法就可以轻松拿到64分（当然如果你在luogu评测机上跑就别想了QAQ）。所以这道题的部分分给的还是挺友善的了。
LOJ 64分代码（如果你去LOJ提交要记得加上文件输入输出哦）：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x){
char c=getchar();x=0;
while(!isdigit(c))c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar();
}
const int MAXN=2e5+5;
int T, n, m1, m2;
ll a[MAXN], b[MAXN];
namespace NF{
const int N=4e3+5, V=N<<1, E=V*20;
int s, t, head[V], e, to[E], fl[E], dis[E], nxt[E];
int flow[E], pv[V], pe[V];
ll d[E], MC, MF;
inline void init(int _s, int _t){
e=1;
s=_s, t=_t;
memset(head, 0, sizeof(head));
}
inline void add_path(int u, int v, int w, ll c){
to[++e]=v, fl[e]=w, dis[e]=c;
nxt[e]=head[u], head[u]=e;
}
inline void add_edge(int u, int v, int w, ll c){
add_path(u, v, w, c);
add_path(v, u, 0, -c);
}
inline bool spfa(){
static bool inq[N];
static queue<int> q;
memset(d, 0x3f, sizeof(d));
d[s]=pv[s]=pv[t]=0;
flow[s]=0x3f3f3f3f;
q.push(s);
inq[s]=true;
while(!q.empty()){
int u=q.front(); q.pop(), inq[u]=false;
for(int i=head[u]; i; i=nxt[i]) if(fl[i]){
int v=to[i], w=fl[i], c=dis[i];
if(d[v]>d[u]+c){
d[v]=d[u]+c;
flow[v]=min(flow[u], w);
pv[v]=u, pe[v]=i;
if(!inq[v]){
q.push(v);
inq[v]=true;
}
}
}
}
return pv[t];
}
inline ll MCMF(){
MF=MC=0;
while(spfa()){
int tmp=flow[t];
MF+=tmp;
MC+=1ll*tmp*d[t];
for(int u=t; pv[u]; u=pv[u]){
int i=pe[u];
fl[i]-=tmp;
fl[i^1]+=tmp;
}
}
return MC;
}
}
namespace bruteforce{
int main(){
int s=n*2+1, t=n*2+2, _s=n*2+3, p1=n*2+4, p2=n*2+5;
NF::init(s, t);
NF::add_edge(s, _s, m1, 0);
NF::add_edge(p1, p2, m1-m2, 0);
for(int i=1; i<=n; ++i){
NF::add_edge(_s, i, 1, -a[i]);
NF::add_edge(i, p1, 1, 0);
NF::add_edge(i+n, t, 1, -b[i]);
NF::add_edge(p2, i+n, 1, 0);
NF::add_edge(i, i+n, 1, 0);
}
printf("%lld\n", -NF::MCMF());
return 0;
}
}
int main(){
// freopen("sequence.in", "r", stdin);
// freopen("sequence.out", "w", stdout);
read(T);
while(T--){
read(n);read(m1);read(m2);
for(int i=1; i<=n; ++i)
read(a[i]);
for(int i=1; i<=n; ++i)
read(b[i]);
if(n<=2000) bruteforce::main();
}
return 0;
}贪心模拟费用流
如何提高费用流效率？我们有个叫“模拟费用流”的东西。说白了，我对模拟费用流的理解就是，在特殊条件允许下，用贪心来取代spfa找最短路，用各种手段（代价取反、分类讨论等等）来模拟退流过程。
那么来看一下这道题如何模拟费用流。
- 首先，不难得出，“自由流”也就是随意配对的方案一定不会比其他方案更劣，那么我们在能流自由流的时候就流自由流。
如何模拟流自由流？显然在还未被配对的
但是，如果选出来的
- 第二，考虑流“限制流”，也就是选取最大的一对下标相等的
a_i 和b_i 。
如何模拟？显然在
请注意，下面的两种方式涉及到模拟退流了！
- 第三，选择一个
a_i 已被配对，而b_i 还未被配对的下标i ，带上一个a_k 还未被配对的下标k 。 （认真理解）
此步非常关键，让我们好好分析一下究竟发生了什么。
画个图就很清晰了。最开始是这样的：
然而之后变成了这样：
那么分析易得，这一次转变的结果是增加了一对下标相同的匹配，而对答案的贡献为
- 第四，也就是情况三的对偶情况，选择一个
b_j 已被配对，而a_j 还未被配对的下标j ，带上一个b_k 还未被配对的下标k 。
同样还是给个图方便理解。先是这样：
变成了这样：
同情况三，这一次转变的结果也是增加了一对下标相同的匹配，而对答案的贡献为
这个时候，我们也就考虑周全了实际费用中的几种流情况，模拟出了“退流”过程，达到了不断“优化调整匹配”的目的，故正确性得到保证，可以开始写了。
然而我认为这道题的难度还不少在实现上（否则进不了NOI），让我们一起仔细想一想怎么实现上述算法。
- 有频繁地根据值来选下标的操作，于是可以用stl优先队列模拟此操作，具体地就是
priority_queue< pair<int, int> > pair第一维存权值，第二维存下标。
-
情况一，需要知道未被匹配的最大的
a 和b 及其下标，于是我们令堆 A0 ，B0 分别存还未被配对的a 和b 。 -
情况二，需要知道未被配对的最大的
a_i+b_i ，于是我们令堆 AB 存未被配对的a_i+b_i -
情况三和四，我们还需要知道“
b_i/a_i 已经被配对而a_i/b_i 还未被配对且a_i/b_i 最大的下标i ”，于是我们分别用堆 A1, B1 来存上述两种情况
综上，时间复杂度优化到了
好，这时候我就兴冲冲地打完了代码，一次过了出题人拿脚出的样例，然后提交……啊，只有4 pts ？？！？
这太戏剧性了，但是不要慌，我们可以对拍，我就把我写的费用流拿来对拍，经过半个下午+一个晚上的艰苦奋斗，终于把这份漏洞百出的代码调 AC 了。于是下面讲几个实现的细节。
-
我们中间会涉及到一些元素被配对，那么他们就应该从他们所在的堆中删除，这个时候可以用一个数组打标记，惰性删除。
-
注意，这一点非常重要！
我们会发现有时候出现这种情况：
显然这样改一下会更优，腾出一个自由流：
这种调整不会改变当前的答案，也不会改变元素在堆中的分布情况，只会还一个一个自由流。
我们把这个操作叫做“adjust”，在代码中就是这个函数。
我们发现这个操作不光需要知道哪些点被配对了，还要知道每个配对的点匹配的是哪个点。于是，我们把上一点说到的打标记用来惰性删除的数组改成一个 int 型的匹配数组就可以了，那么注意在其他的操作中都要对这个数组小心地进行维护，而不是像以前一样只简单的打个标记就行。
在考虑什么时候要 adjust ，很显然，这个操作针对的是被自由匹配的点，那么我们只需要在每出现自由流的时候做这个操作就行了。观察之前画的图，发现情况一直接流自由流和情况三和四会改变原来的自由流，在这几个情况处理后对相应的下标 adjust 一下就好了。
- 关于维护自由流流量：
因为我们操作时有一个优先流自由流的决策 所以要开一个变量 Free 来记录当前还有多少个自由流可以流。
-
每次情况一流一个自由流的时候，判断如果两边选的是不相等的下标就要把 Free 减一。
-
每次 adjust 时候，注意 Free 至少会+1，如果
j=k ，就还要再 +1。 -
但是，情况三和四，也要注意！分别对应之前讲这两种情况的情景图，当
j=k 或i=k 的时候，运气非常好地把自由流消掉了，Free也要+1。
好啦，其他就没什么难点了，把代码放出来，里头有很多注释，这也应该是比较好懂的一份代码了。
#include <bits/stdc++.h>
#define mkp make_pair
#define ft first
#define sd second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef priority_queue< pair<int, int> > heap;
template<class T> inline void read(T& x){
char c=getchar();x=0;
while(!isdigit(c))c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar();
}
const int N=2e5+5;
int T, n, K, L, a[N], b[N], Free, now, type;
ll ans;
heap A0, A1, B0, B1, AB;
//A0, B0: 没被选的的a,b
//A1, B1: 已经被选了对应的b/a但自己没被选的a/b
//AB: a,b都没被选的组合
int mcha[N], mchb[N];
//mcha[i]: a[i]匹配的b[j]的下标j
//mchb[i]: b[i]匹配的a[j]的下标j
inline void del_AB(){//同时根据a，b的匹配情况来删除堆AB中的元素
while(!AB.empty()){
int i=AB.top().sd;
if(mcha[i]||mchb[i]) AB.pop();
else break;
}
}
inline void del_A(heap& A){//根据a的匹配情况来删除堆A0或A1中的元素
while(!A.empty()){
int i=A.top().sd;
if(mcha[i]) A.pop();
else break;
}
}
inline void del_B(heap& B){//根据b的匹配情况来删除堆B0或B1中的元素
while(!B.empty()){
int i=B.top().sd;
if(mchb[i]) B.pop();
else break;
}
}
inline void adjust(int i){//核心：调整操作
if(!mcha[i]||!mchb[i]||mcha[i]==i) return;
int j=mcha[i], k=mchb[i];
mcha[i]=mchb[i]=i, ++Free;//腾出自由流
mcha[k]=j, mchb[j]=k;
if(k==j) ++Free;
}
inline void free_match(){//自由配对
del_A(A0), del_B(B0);
int i=A0.top().sd, j=B0.top().sd;
ans+=1ll*(a[i]+b[j]);
mcha[i]=j, mchb[j]=i;
if(i!=j){
--Free;//消耗自由流
if(!mcha[j]) A1.push(mkp(a[j], j));
if(!mchb[i]) B1.push(mkp(b[i], i));
}
adjust(i), adjust(j);//记得做调整
}
inline void work1(){//选一对a[i]+b[i]
del_AB();
if(!AB.empty()){
int i=AB.top().sd;
if(a[i]+b[i]>now){
now=a[i]+b[i];
type=1;
}
}
}
inline void work2(){//a[i]+b[j] -> a[i]+b[i], a[k]+b[j]
del_B(B1), del_A(A0);
if(B1.empty()) return;
int i=B1.top().sd, k=A0.top().sd;
if(a[k]+b[i]>now){
now=a[k]+b[i];
type=2;
}
}
inline void work3(){//a[i]+b[j] -> a[j]+b[j], a[i]+b[k]
del_A(A1), del_B(B0);
if(A1.empty()) return;
int j=A1.top().sd, k=B0.top().sd;
if(a[j]+b[k]>now){
now=a[j]+b[k];
type=3;
}
}
inline void update1(){//选择了情况一后的更新操作
int i=AB.top().sd;
mcha[i]=mchb[i]=i;
}
inline void update2(){//选择了情况二后的更新操作
int i=B1.top().sd, k=A0.top().sd, j=mcha[i];
mcha[i]=mchb[i]=i;
mcha[k]=j, mchb[j]=k;
if(j==k) ++Free;//腾出自由流
if(!mchb[k]) B1.push(mkp(b[k], k));
adjust(j), adjust(k);
}
inline void update3(){//选择了情况三后的更新操作
int j=A1.top().sd, k=B0.top().sd, i=mchb[j];
mcha[j]=mchb[j]=j;
mcha[i]=k, mchb[k]=i;
if(i==k) ++Free;
if(!mcha[k]) A1.push(mkp(a[k], k));
adjust(i), adjust(k);
}
inline void cls(){//多测清空
ans=0;
while(!A0.empty()) A0.pop();
while(!A1.empty()) A1.pop();
while(!B0.empty()) B0.pop();
while(!B1.empty()) B1.pop();
while(!AB.empty()) AB.pop();
memset(mcha, 0, sizeof(mcha));
memset(mchb, 0, sizeof(mchb));
}
int main(){
// freopen("sequence.in", "r", stdin);
// freopen("sequence.out", "w", stdout);
read(T);
while(T--){
cls();
read(n);read(K);read(L);
for(int i=1; i<=n; ++i)
read(a[i]);
for(int i=1; i<=n; ++i)
read(b[i]);
Free=K-L;//初始化自由流数量
for(int i=1; i<=n; ++i){
A0.push(mkp(a[i], i));
B0.push(mkp(b[i], i));
AB.push(mkp(a[i]+b[i], i));
}
while(K--){
if(Free){//优先自由配对
free_match();
continue;
}
now=0, type=0;
work1();//选一对a[i]+b[i]
work2();//a[i]+b[j] -> a[i]+b[i], a[k]+b[j]
work3();//a[i]+b[j] -> a[j]+b[j], a[i]+b[k]
ans+=1ll*now;
if(type==1) update1();
else if(type==2) update2();
else update3();
}
printf("%lld\n", ans);
}
return 0;
}后记
这是我NOI2019的题目中AC的第四道题，虽然在NOI里不能算难题，可能大佬们写起来觉得挺轻松（所以大佬的题解语言简洁代码灵动，蒟蒻看不懂QAQ），但是还是挺有感触的。有时候你一味想着看题解却可能一无所获（逃）。所以写了这篇比较完整而细致的题解，希望能帮到大家。然而如果看了这篇题解你还是没有懂（应该不会吧啊？），那你不妨想：
有时困境不会对你的垂首乞怜心生恻隐，只会因你的迎难而上肃然起敬。
好啦，这篇题解到此结束了，来了就点个赞（或者踩一脚）再走呗。
由于这是我自己胡搞出来的解法，如果您还有什么疑问或是建议，欢迎到评论区留言，我会尽力回复；如果您发现了我的漏洞，也欢迎到评论区指出或 hack ，我会认真改正！