题解【P5470 [NOI2019] 序列】

command_block · 2021-06-15 22:27:36 · 题解

更严谨的正确性分析。

更自然的非启发式思路。

更强的扩展性。

模拟费用流小记（建议阅读）
NOI2019 简要题解

题意 : 给定两个长度为 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)。

理清思路后代码非常好写。

#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;
}

题解 【P5470 [NOI2019] 序列】

题解【P5470 [NOI2019] 序列】