P5470：NOI2019 序列
题意：给定两个长度 \(n\) 的序列 \(a,b\)。
要求各选出 \(k\) 个数，使得这 \(2k\) 个数之和最大，且两个序列选出的数至少有 \(l\) 个位置相同。
\(n\le 2\times 10^5\)。
command_block 的题解 但是这个貌似有一些小问题，后文有写。
算法：模拟费用流。
【费用流模型】
关键点在于把至少 \(l\) 个位置相同改成至多 \(k-l\) 个位置不同。
可以把两个序列共同视作一个二分图，各自作为左右部；两个序列的 \(k\) 个数视作一个大小为 \(k\) 的匹配，用二分图式的建模。
具体而言，把 \(a_{1\sim n}\) 抽象为 \(n\) 个点，\(b_{1\sim n}\) 抽象为 \(n\) 个点。
\(S\rightarrow a_{1\sim n}\)，容量 \(1\) 费用 \(a_i\)（每个数只能选一次）。
\(b_{1\sim n}\rightarrow T\)，容量 \(1\) 费用 \(b_i\)。
\(a_i\rightarrow b_i\)，容量 \(1\) 费用 \(0\)。
新建两个点 \(u,v\)，\(u\rightarrow v\) 容量 \(k-l\) 费用 \(0\)。如果流了 \(u\rightarrow v\) 的边，表示这条增广路对应了一次位置不同的匹配。
\(a_{1\sim n}\rightarrow u\)，\(v\rightarrow b_{1\sim n}\)，容量 \(1\) 费用 \(0\)。
注意最多选 \(k\) 个匹配，所以加上一个 \(S'\rightarrow S\)，容量 \(k\) 费用 \(0\)。
于是这张图的最大费用最大流就是问题的答案。直接建图跑费用流好像能拿 \(50\) 分。
【模拟费用流】
直接跑费用流太慢了，因为图的结构比较简单，考虑模拟费用流。
考虑有多少种本质不同的增广路，用分类讨论的方式会更好找。（下面就不带 \(S'\) 了，直接把 \(S\) 当作源点）
-
不经过点 \(u,v\) 的：\(S\rightarrow a_i\rightarrow b_i\rightarrow T\)。
-
经过点 \(u\) 却不经过点 \(v\) 的：\(S\rightarrow a_i\rightarrow u\rightarrow a_j\rightarrow b_j\rightarrow T\)。
-
经过点 \(v\) 却不经过点 \(u\) 的：\(S\rightarrow a_i\rightarrow b_i\rightarrow v\rightarrow b_j\rightarrow T\)。
-
经过点 \(u,v\) 的。
-
经过边 \((u,v)\) 的有两种：\(S\rightarrow a_i\rightarrow u\rightarrow v\rightarrow b_j\rightarrow T\) 和 \(S\rightarrow a_i\rightarrow b_i\rightarrow v\rightarrow u\rightarrow a_j\rightarrow b_j\rightarrow T\)。
-
不经过边 \((u,v)\) 的有两种：\(S\rightarrow a_i\rightarrow u\rightarrow a_j\rightarrow b_j\rightarrow v\rightarrow b_k\rightarrow T\) 和 \(S\rightarrow a_i\rightarrow b_i\rightarrow v\rightarrow b_j\rightarrow a_j\rightarrow u\rightarrow a_k\rightarrow b_k\rightarrow T\)。
-
天啊！这居然有 \(7\) 种不同的增广路！！！这实在是太复杂了。
如果从这里就开始写，要判断 \(7\) 种增广路。但我们能通过分析减至 \(5\) 种。
【简化问题】
上面 "经过点 \(u,v\) 但不经过 \((u,v)\)" 的两种增广路都可以被省掉。
先说较长的那一条：\(S\rightarrow a_i\rightarrow b_i\rightarrow v\rightarrow b_j\rightarrow a_j\rightarrow u\rightarrow a_k\rightarrow b_k\rightarrow T\)。
—— 摘自 command_block 的博客
然后考虑 \(S\rightarrow a_i\rightarrow u\rightarrow a_j\rightarrow b_j\rightarrow v\rightarrow b_k\rightarrow T\)。同样考虑它应用后的影响。发现它的形式其实和 \(S\rightarrow a_i\rightarrow u\rightarrow v\rightarrow b_j\rightarrow T\) 类似。区别就在于这一条增广路使原本的一条使用了 \(u\rightarrow v\) 的路径变得不使用，同时还仍旧保持贡献不变。（翻译一下就是原本拐到上面的变成平着的）
所以我们只需要 \(5\) 种增广路即可。
【Code】
消耗时间 4h。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
int T;
int n, K, L; //n个数，选K个，至少L个相同
ll a[N], b[N];
bool visa[N] = {}, visb[N] = {};
bool hfa[N] = {}, hfb[N] = {}; //hfa[i]=true表示ai流过ai->u的边
ll ans = 0;
int fre; //自由流剩余流量
typedef pair<ll, ll> pii;
#define mk_pr make_pair
priority_queue<pii> q1;
priority_queue<pii> qa, qb, qa2, qb2;
//q1:ai+bi最大
//qa:s->ai没用过 ai最大，qb:bi->t没用过 bi最大
//qa2:bk用过自由的（hfb[k]=true） s->ak没用过的（visa[k]=false） 最大的ak
//qb2:ak用过自由的（hfa[k]=true）bk->t没用过的（visb[k]=false） 最大的bk
//visa[i]=true表示s->ai流过
//hfa[i]=true表示ai->u流过
/*
五种增广路：
1. s->ai->bi->t 收益ai+bi
用到q1
2. s->ai->u->v->bj->t 消耗自由流1 收益ai+bj
用到qa,qb
3. s->ai->bi->v->u->ak->bk->t 增加自由流1 收益ai+bk
用到qa2,qb2
4. s->ai->u->aj->bj->t 收益ai+bj
用到qb2和qa
5. s->ai->bi->v->bj->t 收益ai+bj
用到qa2和qb
*/
//考虑应用增广路对q的影响！！！
void all_pop() {
while (!q1.empty() && (visa[q1.top().second] || visb[q1.top().second]))
q1.pop();
while (!qa.empty() && visa[qa.top().second])
qa.pop();
while (!qb.empty() && visb[qb.top().second])
qb.pop();
while (!qa2.empty() && (!hfb[qa2.top().second] || visa[qa2.top().second])) {
//printf("Pop qa2\n");
qa2.pop();
}
while (!qb2.empty() && (!hfa[qb2.top().second] || visb[qb2.top().second]))
qb2.pop();
}
void pfm1() {
ans += a[q1.top().second] + b[q1.top().second];
visa[q1.top().second] = true;
visb[q1.top().second] = true;
q1.pop();
}
void pfm2() {
//q1:ai+bi最大
//qa:s->ai没用过 ai最大，qb:bi->t没用过 bi最大
//qa2:bk用过自由的（hfb[k]=true） s->ak没用过的（visa[k]=false） 最大的ak
//qb2:ak用过自由的（hfa[k]=true）bk->t没用过的（visb[k]=false） 最大的bk
fre--;
ans += a[qa.top().second] + b[qb.top().second];
visa[qa.top().second] = true;
visb[qb.top().second] = true;
hfa[qa.top().second] = true;
hfb[qb.top().second] = true;
if (hfa[qa.top().second] && hfb[qa.top().second]) {
hfa[qa.top().second] = hfb[qa.top().second] = false;
fre++;
}
if (hfa[qb.top().second] && hfb[qb.top().second]) {
hfa[qb.top().second] = hfb[qb.top().second] = true;
fre++;
}
//此处有增加其他可能性
if (hfb[qb.top().second] && !visa[qb.top().second]) {
qa2.push(mk_pr(a[qb.top().second], qb.top().second));
}
if (hfa[qa.top().second] && !visb[qa.top().second])
qb2.push(mk_pr(b[qa.top().second], qa.top().second));
qa.pop();
qb.pop();
}
void pfm3() {
// 3. s->ai->bi->v->u->ak->bk->t 增加自由流1 收益ai+bk
// 用到qa2,qb2
//qa:s->ai没用过 ai最大，qb:bi->t没用过 bi最大
//qa2:bk用过自由的（hfb[k]=true） s->ak没用过的（visa[k]=false） 最大的ak
//qb2:ak用过自由的（hfa[k]=true）bk->t没用过的（visb[k]=false） 最大的bk
fre++;
ans += a[qa2.top().second] + b[qb2.top().second];
visa[qa2.top().second] = true;
visb[qb2.top().second] = true;
hfa[qb2.top().second] = false;
hfb[qa2.top().second] = false;
qa2.pop();
qb2.pop();
}
void pfm4() {
//4. s->ai->u->aj->bj->t 收益ai+bj
//用到qb2和qa
ans += a[qa.top().second] + b[qb2.top().second];
visa[qa.top().second] = true;
visb[qb2.top().second] = true;
hfa[qb2.top().second] = false;
hfa[qa.top().second] = true;
if (hfa[qa.top().second] && hfb[qa.top().second]) {
hfa[qa.top().second] = hfb[qa.top().second] = false;
fre++;
}
if (hfa[qa.top().second] && !visb[qa.top().second])
qb2.push(mk_pr(b[qa.top().second], qa.top().second));
qa.pop();
qb2.pop();
}
void pfm5() {
//5. s->ai->bi->v->bj->t 收益ai+bj
//用到qa2和qb
ans += a[qa2.top().second] + b[qb.top().second];
visa[qa2.top().second] = true;
visb[qb.top().second] = true;
hfb[qa2.top().second] = false;
hfb[qb.top().second] = true;
if (hfb[qb.top().second] && hfa[qb.top().second]) {
hfb[qb.top().second] = hfa[qb.top().second] = false;
fre++;
}
if (hfb[qb.top().second] && !visa[qb.top().second]) {
qa2.push(mk_pr(a[qb.top().second], qb.top().second));
}
qa2.pop();
qb.pop();
}
void slv() {
cin >> n >> K >> L;
while (!q1.empty())
q1.pop();
while (!qa.empty())
qa.pop();
while (!qb.empty())
qb.pop();
while (!qa2.empty())
qa2.pop();
while (!qb2.empty())
qb2.pop();
for (int i = 1; i <= n; i++)
visa[i] = visb[i] = hfa[i] = hfb[i] = false;
for (int i = 1; i <= n; i++) {
cin >> a[i];
qa.push(mk_pr(a[i], i));
}
for (int i = 1; i <= n; i++) {
cin >> b[i];
qb.push(mk_pr(b[i], i));
q1.push(mk_pr(a[i] + b[i], i));
}
ans = 0;
fre = K - L; //自由流剩余流量
for (int i = 1; i <= K; i++) {
all_pop();
ll t1 = -1, t2 = -1, t3 = -1, t4 = -1, t5 = -1;
if (!q1.empty())
t1 = q1.top().first;
if (!qa.empty() && !qb.empty() && fre > 0)
t2 = qa.top().first + qb.top().first;
if (!qa2.empty() && !qb2.empty() && fre < K - L)
t3 = qa2.top().first + qb2.top().first;
if (!qb2.empty() && !qa.empty())
t4 = qb2.top().first + qa.top().first;
if (!qa2.empty() && !qb.empty())
t5 = qa2.top().first + qb.top().first;
ll mx = max(max(max(max(t1, t2), t3), t4), t5);
if (t1 == mx)
pfm1();
else if (t2 == mx)
pfm2();
else if (t3 == mx)
pfm3();
else if (t4 == mx)
pfm4();
else
pfm5();
}
cout << ans << endl;
}
int main() {
cin >> T;
while (T--)
slv();
return 0;
}