题解 【P5470 [NOI2019] 序列】

更严谨的正确性分析。 更自然的非启发式思路。 更强的扩展性。 **广告** ： - [模拟费用流小记](https://www.luogu.com.cn/blog/command-block/mu-ni-fei-yong-liu-xiao-ji) （建议阅读） - [NOI2019 简要题解](https://www.luogu.com.cn/blog/command-block/noi2019-jian-yao-ti-xie) ------------ **题意** : 给定两个长度为 $n$ 的正整数序列 $\{a_i\}$ 与 $\{b_i\}$。 分别对两个序列各指定**恰好** $K$ 个下标，要求**至少**有 $L$ 个下标在两个序列中都被指定，使得这 $2K$ 个下标在序列中对应的元素的总和**最大**。 多组数据， $T\leq 10,n\leq 2\times 10^5,\sum n\leq 10^6$。 ------------ - **费用流模型** 至少有 $L$ 个下标相同，即至多有 $K-L$ 个下标不同。 - 对每个 $i$ : 连边 $S\rightarrow a_i$ ，容量为 $1$ ，边权为 $a_i$。 连边 $b_i\rightarrow T$ ，容量为 $1$ ，边权为 $b_i$。 连边 $a_i\rightarrow b_i$ ，无权，表示选择一对相同的下标。 新建点 $U,V$ ，连边 $U\rightarrow V$ ，无权，容量为 $K-L$ （称为自由流量），表示不同的下标。 对每个 $i$ ，连边 $a_i\rightarrow U,\ V\rightarrow b_i$。 限制流量为 $K$ ，求解最大费用最大流即可。 直接跑费用流可以获得 $40\sim 64$ 分。 ------------ - **模拟费用流** 首先观察建图 :  除了和 $S,T$ 直接相连的边以外，其他边的边权均为 $0$。 考虑直接模拟 EK 算法的过程。 所有和 $S,T$ 直接相连的边不会退流（可以忽略反向边），而中间的边可能因为退流而发生方向的改变（添加）。 考虑所有可能的增广路形态，以及它们的实际意义。 由于同一个点至多经过一次，增广路形态不会很多。  其中红色为增广路。  其中红色为新选择的点，黑色为已选的点。绿色边为原来的配对，红色边为新的配对。 具体方案如下。记这一轮选择一对 $(a_i,b_j)$。 - ① : $i=j$。 - ② : $i\neq j$ ，消耗一单位自由流量。 - ③ : 将 $a_i$ 与 $b_i$ （必须已选）配对，将 $b_j$ 与 $a_j$ （必须已选） 配对。增加一单位自由流量。 - ④ ：将 $a_i$ 与 $b_i$ （必须已选）配对，将 $b_j$ 与原来与 $b_i$ 配对的 $a_k$ 配对。 - ⑤ ：将 $b_i$ 与 $a_i$ （必须已选）配对，将 $a_j$ 与原来与 $a_i$ 配对的 $b_k$ 配对。 单观察图的话，还可能有下面的这种增广路 ：  （此时 $u,v$ 都被经过了，故不可能有更复杂的增广路） 考虑这类增广路的实际意义，如右图。其中绿色是原来的连接情况，红色是后来的连接情况。 然而，总是存在更优的连接方式（如蓝色），故这类增广路不优。 我们用堆维护上述五种转移。 两侧分别用两个堆 $q_a,q_b$ 维护未选的数的 $\max$。 用堆 $q$ 维护未选的数的 $a_i+b_i$ 的 $\max$。 再用两个堆 $q_a',q_b'$ 维护“本侧未选中，但另一侧选中”的数的 $\max$。 记 $q,q_a,q_b,q_a',q_b'$ 堆顶为 $s,a,b,a',b'$。（若不存在则为 $-\infty$） - ① ： $s$。 - ② ： $a+b$。当有自由流量时才生效。 - ③ ： $a'+b'$。自由流量加一。 - ④ ： $a'+b$。 - ⑤ ： $a+b'$。 五种方案取 $\max$ 即可。 复杂度为 $O(n\log n)$。 理清思路后代码非常好写。 ```cpp #include<algorithm> #include<cstdio> #include<queue> #define Pr pair<int,int> #define fir first #define sec second #define mp make_pair #define ll long long #define MaxN 200500 using namespace std; const int INF=1000000000; priority_queue<Pr> q,qa,qb,qa2,qb2; int n,k,l,a[MaxN],b[MaxN]; bool visa[MaxN],visb[MaxN]; void seta(int p) {visa[p]=1;if (!visb[p])qb2.push(mp(b[p],p));} void setb(int p) {visb[p]=1;if (!visa[p])qa2.push(mp(a[p],p));} void solve() { scanf("%d%d%d",&n,&k,&l);l=k-l; for (int i=1;i<=n;i++)scanf("%d",&a[i]); for (int i=1;i<=n;i++)scanf("%d",&b[i]); for (int i=1;i<=n;i++){ visa[i]=visb[i]=0; q.push(mp(a[i]+b[i],i)); qa.push(mp(a[i],i)); qb.push(mp(b[i],i)); } q.push(mp(-INF,0)); qa.push(mp(-INF,0));qb.push(mp(-INF,0)); qa2.push(mp(-INF,0));qb2.push(mp(-INF,0)); ll ans=0; for (int i=1;i<=k;i++){ while(visa[q.top().sec]||visb[q.top().sec])q.pop(); while(visa[qa.top().sec])qa.pop(); while(visb[qb.top().sec])qb.pop(); while(visa[qa2.top().sec])qa2.pop(); while(visb[qb2.top().sec])qb2.pop(); Pr now=q.top(),nowa=qa.top(),nowb=qb.top(); int op=1,mx=now.fir; Pr nowa2=qa2.top(),nowb2=qb2.top(); if (mx<nowa2.fir+nowb2.fir){ mx=nowa2.fir+nowb2.fir; op=3; } if (mx<nowa2.fir+nowb.fir){ mx=nowa2.fir+nowb.fir; op=4; } if (mx<nowa.fir+nowb2.fir){ mx=nowa.fir+nowb2.fir; op=5; } if (nowa.sec!=nowb.sec&&l) if (mx<nowa.fir+nowb.fir){ mx=nowa.fir+nowb.fir; op=2; } ans+=mx; if (op==1){seta(now.sec);setb(now.sec);} if (op==2){seta(nowa.sec);setb(nowb.sec);l--;} if (op==3){seta(nowa2.sec);setb(nowb2.sec);l++;} if (op==4){seta(nowa2.sec);setb(nowb.sec);} if (op==5){seta(nowa.sec);setb(nowb2.sec);} } printf("%lld\n",ans); while(!q.empty())q.pop(); while(!qa.empty())qa.pop();while(!qb.empty())qb.pop(); while(!qa2.empty())qa2.pop();while(!qb2.empty())qb2.pop(); } int main() { freopen("sequence3.in","r",stdin); int T;scanf("%d",&T); while(T--)solve(); return 0; } ```