大致题意： 给定两个长度为\(n\)的整数序列，要求在两个序列中分别选出\(k\)个数，其中至少有\(l\)对数下标相同，使得数的总和最大。
费用流
模拟费用流，自然就是在费用流的基础上模拟。
因此，我们首先要知道如何暴力费用流。
建图如下：
解释：一般的边对应选出一对下标相同的数的情况。由于能任选\(k-l\)对，因此任选边\(p\rightarrow p'\)的流量是\(k-l\)。
然而直接跑费用流显然是无法通过此题的。
模拟费用流
模拟费用流是对费用流的模拟，接下来的每种情况其实都在费用流的图中有着对应的流法。
考虑\(p\rightarrow p'\)肯定是最优的边，因此我们先贪心将其流满。
具体地，我们对两个序列各自开一个堆，每次选出还未选择过的\(a\)中最大元素\(a_u\)和\(b\)中最大元素\(b_v\)，将总流量\(k\)以及\(p\rightarrow p'\)的容量减\(1\)。
（\(S\rightarrow S'\rightarrow u\rightarrow p\rightarrow p'\rightarrow v'\rightarrow T\)）
然而如果\(b_u\)或者\(a_v\)已经被选择过了，那么我们可以让它们不流\(p\rightarrow p'\)这条任选边，而是从一般的边上走，此时可以将\(p\rightarrow p'\)的容量加\(1\)。
（\(S\rightarrow S'\rightarrow u\rightarrow u'\rightarrow T\)或\(S\rightarrow S'\rightarrow v\rightarrow v'\rightarrow T\)）
流满了\(p\rightarrow p'\)，接下来我们有\(3\)种选择：
- 选择一对都未选过的\(a_x,b_x\)。（\(S\rightarrow S'\rightarrow x\rightarrow x'\rightarrow T\)）
- 选择一个最大的\(a_u\)，以及一个\(a_v\)已经被选过的\(b_v\)。相当于将原先与\(a_v\)通过任选边连接的\(b\)转送给\(a_u\)，而\(a_v\)和\(b_v\)自己走一般边（但要注意如果\(b_u\)也已经被选过了，需要将\(p\rightarrow p'\)容量加\(1\)重新执行一开始的操作）。（\(S\rightarrow S'\rightarrow u\rightarrow p\leftarrow v\rightarrow v'\rightarrow T\)，其中左箭头表示走反向边，即退流操作）
- 选择一个最大的\(b_v\)，以及一个\(b_u\)已经被选过的\(a_u\)。同上。
具体实现也就是开五个堆。。。（其中两个可以延续之前的）
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 200000
using namespace std;
int n,k,l,a[N+5],b[N+5],p[N+5],q[N+5];struct Data
{
int p,v;I Data(CI x=0,CI y=0):p(x),v(y){}
I bool operator < (Con Data& o) Con {return v<o.v;}
};priority_queue<Data> A,B,A_,B_,C;
//A,B存储两个序列中所有未选的元素；A_,B_存储未选但对应元素已被选的元素；C存储下标相同都未被选的元素对
class FastIO
{
private:
#define FS 100000
#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)
#define D isdigit(c=tc())
char c,*A,*B,FI[FS];
public:
I FastIO() {A=B=FI;}
Tp I void read(Ty& x) {x=0;W(!D);W(x=(x<<3)+(x<<1)+(c&15),D);}
}F;
int main()
{
RI Tt,i,t,x,y,z;long long ans;Data u,v;F.read(Tt);W(Tt--)
{
//为了使代码更为简洁，使用了大量#define，请见谅
#define PA(x) (p[x]=1,q[x]?1:(B_.push(Data(x,b[x])),0))//选择a[x]，打上标记，判断b[x]是否已经选择，没有还要放到堆B_中
#define PB(x) (q[x]=1,p[x]?1:(A_.push(Data(x,a[x])),0))//选择b[x]，打上标记，判断a[x]是否已经选择，没有还要放到堆A_中
#define G(g,H) (g=H.top(),H.pop())//取出H的堆顶存放到g中
#define T(H) (H.empty()?-1e9:H.top().v)//询问堆顶的值，堆为空时返回-INF
W(!A.empty()) A.pop();W(!B.empty()) B.pop();//清空
W(!A_.empty()) A_.pop();W(!B_.empty()) B_.pop();W(!C.empty()) C.pop();//清空
F.read(n),F.read(k),F.read(l),t=k-l;//t记录任选边容量
for(i=1;i<=n;++i) F.read(a[i]),A.push(Data(i,a[i])),p[i]=0;//读入并初始化堆A
for(i=1;i<=n;++i) F.read(b[i]),B.push(Data(i,b[i])),q[i]=0;//读入并初始化堆B
ans=0;W(k&&t&&!A.empty()) --k,--t,G(u,A),G(v,B),ans+=u.v+v.v,PA(u.p)&&++t,PB(v.p)&&++t;//先将任选边流满，若对应元素已选择则将容量加1
for(i=1;i<=n;++i) !p[i]&&!q[i]&&(C.push(Data(i,a[i]+b[i])),0);//将都未被选的元素堆放入堆中
W(k)
{
W(!C.empty()&&(p[C.top().p]||q[C.top().p])) C.pop();//弹去不合法元素
W(!A.empty()&&p[A.top().p]) A.pop();W(!A_.empty()&&p[A_.top().p]) A_.pop();//弹去不合法元素
W(!B.empty()&&q[B.top().p]) B.pop();W(!B_.empty()&&q[B_.top().p]) B_.pop();//弹去不合法元素
--k,x=T(C),y=T(A)+T(B_),z=T(A_)+T(B);//三种情况
if(x>=y&&x>=z) {G(u,C),ans+=x,p[u.p]=q[u.p]=1;continue;}//选中元素对
y>=z?(G(u,A),G(v,B_),ans+=y,q[v.p]=1,PA(u.p)&&++t)//注意若b[u]已选择则将任选边容量加1
:(G(u,A_),G(v,B),ans+=z,p[u.p]=1,PB(v.p)&&++t);//注意若a[v]已选择则将任选边容量加1
W(k&&t)//与之前的操作过程一致
{
W(!A.empty()&&p[A.top().p]) A.pop();W(!B.empty()&&q[B.top().p]) B.pop();//弹去不合法元素
--k,--t,G(u,A),G(v,B),ans+=u.v+v.v,PA(u.p)&&++t,PB(v.p)&&++t;//可从上面直接复制下来
}
}printf("%lld\n",ans);
}return 0;
}