题解 【P5470 [NOI2019] 序列】
command_block
2021-06-15 22:27:36
更严谨的正确性分析。
更自然的非启发式思路。
更强的扩展性。
**广告** :
- [模拟费用流小记](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$ 分。
------------
- **模拟费用流**
首先观察建图 :
![](https://cdn.luogu.com.cn/upload/image_hosting/5863chlh.png)
除了和 $S,T$ 直接相连的边以外,其他边的边权均为 $0$。
考虑直接模拟 EK 算法的过程。
所有和 $S,T$ 直接相连的边不会退流(可以忽略反向边),而中间的边可能因为退流而发生方向的改变(添加)。
考虑所有可能的增广路形态,以及它们的实际意义。
由于同一个点至多经过一次,增广路形态不会很多。
![](https://cdn.luogu.com.cn/upload/image_hosting/xe956808.png)
其中红色为增广路。
![](https://cdn.luogu.com.cn/upload/image_hosting/o0hmwgac.png)
其中红色为新选择的点,黑色为已选的点。绿色边为原来的配对,红色边为新的配对。
具体方案如下。记这一轮选择一对 $(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$ 配对。
单观察图的话,还可能有下面的这种增广路 :
![](https://cdn.luogu.com.cn/upload/image_hosting/tgoycu71.png)
(此时 $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;
}
```