【题解】[NOI2019] 序列 贪心模拟费用流 —Qiuly

$20\ pts$ 暴搜

直接枚举 $\rm{L}$ 集合即可。

$40\ pts\ \rm{DP}$

暴力 $O(n^4)\ \rm{DP}$ ，即设 $f_{i,a,b,c}$ 表示选到第 $i$ 个，第一个序列选了 $a$ 个，第二个序列选了 $b$ 个，两个序列选的数中下标一样的有 $c$ 个，直接转移即可。

$64\ pts$ 费用流

费用流。

首先，将 $\rm{S}$ 和所有 $\rm{A}$ 序列的元素连边，费用为元素的值，然后 $\rm{A_i}$ 向 $\rm{B_i}$ 连 $0$ 边，$\rm{B}$ 序列向 $\rm{T}$ 连费用为元素的值的边即可，这些边的流量全部为 $1$ 。

题目要求为选出来的数至少 $\rm{L}$ 个下标相同的，这意味着可以选出最多 $\rm{K-L}$ 个下标不同的数。于是 $\rm{A}$ 的每一个元素向 $C$ 连费用为 $0$ 流量为 $1$ 的边，同样 $\rm{D}$ 向 $\rm{B}$ 的所有元素连费用为 $0$ 边权为 $1$ 的边。最后在 $\rm{C}$ 和 $\rm{D}$ 之间连接一条费用为 $0$ 流量为 $\rm{K-L}$ 的边即可。

注意因为是要最大值，所以上面每一条边的费用全部变为其相反数即可。

$100\ pts$ 贪心模拟费用流

滑稽吧，就像 $\rm{NOI2017}$蔬菜 一样。

首先排序把最大的 $\rm{K-L}$ 个组合送进去，也就是让这些组合流过 $\rm{C \rightarrow D}$ 这条边。然后剩下 $\rm{L}$ 个组合慢慢枚举，$s_i$ 表示第 $i$ 对的使用情况，如果为 $1$ 代表 $A_i$ 被用了，$2$ 代表 $B_i$ 被用了，$3$ 代表都被用了。如果 $s_i$ 为 $3$ 意味着第 $i$ 对完全不需要占 $\rm{C \rightarrow D}$ 的流量，提出来就好。

具体看代码。

#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=1e6+5;
ll ans,v1,v2,v3,maxv;
int T,n,K,L,c1,c2,res,a[N],b[N],s[N],id[N];
bool cmp_a(int x,int y) {return a[x]>a[y];}
bool cmp_b(int x,int y) {return b[x]>b[y];}
struct Node_a{int id;bool operator < (const Node_a x) const {return a[id]<a[x.id];}}tmpa;
struct Node_b{int id;bool operator < (const Node_b x) const {return b[id]<b[x.id];}}tmpb;
struct Node_c{int id;bool operator < (const Node_c x) const {return a[id]+b[id]<a[x.id]+b[x.id];}}tmpc;
priority_queue<Node_a> lora,nofa;
priority_queue<Node_b> lorb,nofb;
priority_queue<Node_c> lorc;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x; 
}

void clear_heap() {
    v1=v2=v3=c1=c2=res=0;
    while(!lora.empty()) lora.pop();while(!lorb.empty()) lorb.pop();while(!lorc.empty()) lorc.pop();
    while(!nofa.empty()) nofa.pop();while(!nofb.empty()) nofb.pop();
}

int main() {
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    IN(T);while(T--) {
        IN(n),IN(K),IN(L),ans=0;
        for(int i=1;i<=n;++i) IN(a[i]);
        for(int i=1;i<=n;++i) IN(b[i]);
        for(int i=1;i<=n;++i) s[i]=0,id[i]=i;
        sort(id+1,id+1+n,cmp_a);for(int i=1;i<=K-L;++i) s[id[i]]|=1,ans+=a[id[i]];
        sort(id+1,id+1+n,cmp_b);for(int i=1;i<=K-L;++i) s[id[i]]|=2,ans+=b[id[i]];
        clear_heap();
        for(int i=1;i<=n;++i) {
            tmpa.id=tmpb.id=tmpc.id=i;
            if(!s[i]) lora.push(tmpa),lorb.push(tmpb),lorc.push(tmpc);
            else if(s[i]==1) lorb.push(tmpb),nofb.push(tmpb);
            else if(s[i]==2) lora.push(tmpa),nofa.push(tmpa);
            else ++res;
        }
        while(L--) {
            while(!lora.empty()&&(s[lora.top().id]&1)) lora.pop();
            while(!nofa.empty()&&(s[nofa.top().id]^2)) nofa.pop();
            while(!lorb.empty()&&(s[lorb.top().id]&2)) lorb.pop();
            while(!nofb.empty()&&(s[nofb.top().id]^1)) nofb.pop();
            while(!lorc.empty()&&s[lorc.top().id]) lorc.pop();
            if(res) {
                int i=lora.top().id,j=lorb.top().id;
                ans+=a[i]+b[j],--res,s[i]|=1,s[j]|=2;
                if(s[i]^3) tmpb.id=i,nofb.push(tmpb);
                if(s[j]^3) tmpa.id=j,nofa.push(tmpa);
                if(i==j) ++res;
                else {if(s[i]==3)++res;if(s[j]==3)++res;}
                continue;
            }
            int i1,i2,i3,j1,j2;
            if(!nofb.empty()) i1=lora.top().id,j1=nofb.top().id,v1=a[i1]+b[j1],c1=(s[i1]==2)?1:0;
            if(!nofa.empty()) i2=lorb.top().id,j2=nofa.top().id,v2=b[i2]+a[j2],c2=(s[i2]==1)?1:0;
            if(!lorc.empty()) i3=lorc.top().id,v3=a[i3]+b[i3];
            maxv=max(v1,max(v2,v3)),ans+=maxv;
            if(v1==v2&&v1==maxv) {
                if(c1>c2) {s[i1]|=1,s[j1]|=2;if(s[i1]^3) nofb.push((Node_b){i1});else res++;}
                else {s[i2]|=2,s[j2]|=1;if(s[i2]^3) nofa.push((Node_a){i2});else res++;}
            } 
            else if(v1==maxv) {s[i1]|=1,s[j1]|=2;if(s[i1]^3) nofb.push((Node_b){i1});else res++;}
            else if(v2==maxv) {s[i2]|=2,s[j2]|=1;if(s[i2]^3) nofa.push((Node_a){i2});else res++;}
            else if(v3==maxv) lorc.pop(),s[i3]=3;
        }
        printf("%lld\n",ans);
    }
    return 0;
}