Luogu

LOJ

分析

至少有 $L$ 个下标相同 $\Longleftrightarrow$ 至多有 $K-L$ 个下标不同。

考虑一个费用流模型，即从源点向 $a$ 中所有点连容量为 $1$、费用为 $a_i$ 的边，从 $b$ 中所有点向汇点连容量为 $1$、费用为 $b_i$ 的边，从 $a_i$ 向 $b_i$ 连容量为 $1$、费用为 $0$ 的边，再新建两个点 $C,D$，从 $C$ 向 $D$ 连容量为 $K-L$、费用为 $0$ 的边，从 $a$ 中所有点向 $C$ 连边，从 $D$ 向 $b$ 中所有点连边。这样子求流量为 $K$ 时的最大费用即为答案。

考虑模拟费用流。显然我们会优先流 $C\to D$，因为此时可能的收益最大。当 $C\to D$ 这条边满流时我们有如下选择：

• 选一个 $a_i+b_i$。
• 选一个 $b_i$ 已经匹配了的 $a_i$ 和 $b_j$ 匹配。
• 选一个 $a_i$ 已经匹配了的 $b_i$ 和 $a_j$ 匹配。

于是我们开五个堆，分别维护未匹配的 $a_i$ 的最大值、未匹配的 $b_i$ 的最大值、未匹配的 $a_i+b_i$ 的最大值、$b_i$ 已经匹配了的 $a_i$ 的最大值、$a_i$ 已经匹配了的 $b_i$ 的最大值，每次三种情况比较一下即可。

实现时需要维护 $C\to D$ 弧的残量已经每个 $a_i$、$b_i$ 是否已经匹配，写起来需要注意各种不会减少（甚至可能增加） $C\to D$ 弧残量的情况。

代码

// ===================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define mp make_pair
#define fi(x) (x.first)
#define se(x) (x.second)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,K,L,a[N],b[N],vA[N],vB[N];
priority_queue<pair<int,int> > QA,QB,QAB,FA,FB;

int main() {
    int T=read();
    while (T--) {
        n=read(),K=read(),L=read();
        for (int i=1;i<=n;++i) a[i]=read();
        for (int i=1;i<=n;++i) b[i]=read();

        while (!QA.empty()) QA.pop();
        while (!QB.empty()) QB.pop();
        while (!QAB.empty()) QAB.pop();
        while (!FA.empty()) FA.pop();
        while (!FB.empty()) FB.pop();
        for (int i=1;i<=n;++i) vA[i]=vB[i]=0;

        for (int i=1;i<=n;++i)
            QA.push(mp(a[i],i)),QB.push(mp(b[i],i)),QAB.push(mp(a[i]+b[i],i));
        ll ans=0,cap=K-L;
        for (int f=1;f<=K;++f) {
            while (!QA.empty()&&vA[se(QA.top())]) QA.pop();
            while (!QB.empty()&&vB[se(QB.top())]) QB.pop();
            if (cap) {
                int i=se(QA.top()),j=se(QB.top()); QA.pop(),QB.pop();
                --cap; ans+=a[i]+b[j]; vA[i]=vB[j]=1;
                if (i==j) ++cap,QAB.pop();
                else {
                    if (vB[i]) ++cap,FA.pop();
                    else FB.push(mp(b[i],i));
                    if (vA[j]) ++cap,FB.pop();
                    else FA.push(mp(a[j],j));
                }
            } else {
                auto QABt=QAB.empty()?mp(0,0):QAB.top();
                while (!QAB.empty()&&(vA[se(QABt)]||vB[se(QABt)]))
                    QAB.pop(),QABt=QAB.empty()?mp(0,0):QAB.top();
                auto QAt=QA.empty()?mp(0,0):QA.top();
                auto QBt=QB.empty()?mp(0,0):QB.top();
                auto FAt=FA.empty()?mp(-fi(QBt),0):FA.top();
                auto FBt=FB.empty()?mp(-fi(QAt),0):FB.top();
                int wAB=fi(QABt),wA=fi(FAt)+fi(QBt),wB=fi(QAt)+fi(FBt);
                if (wAB>=wA&&wAB>=wB) {
                    ans+=wAB,vA[se(QABt)]=vB[se(QABt)]=1;
                } else if (wA>=wB) {
                    ans+=wA,vA[se(FAt)]=vB[se(QBt)]=1,FA.pop(),QB.pop();
                    if (vA[se(QBt)]) FB.pop(),++cap;
                    else FA.push(mp(a[se(QBt)],se(QBt)));
                } else {
                    ans+=wB,vA[se(QAt)]=vB[se(FBt)]=1,FB.pop(),QA.pop();
                    if (vB[se(QAt)]) FA.pop(),++cap;
                    else FB.push(mp(b[se(QAt)],se(QAt)));
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}