题解 CF730I 【Olympiad in Programming and Sports】

· · 题解

复习联赛

考虑费用流模型：

V=\{S,T,A,B,1,2,\cdots,n\} E=\{(S,A,lim_1,0),(S,B,lim_2,0)\}\cup \{(A,i,1,a_i)\}\cup \{(B,i,1,b_i)\}\cup \{(i,T,1,0)\}

观察每次增广，可以发现是四种情况之一：

使用 4 个堆维护这个过程即可，时间复杂度为 O(n\log n)。由于本题数据范围小，代码全程使用 int：

#include<cstdio>
#include<queue>
using namespace std;

const int MAXN=1e5+5,INF=2147483647;
int N,P,S,a[MAXN],b[MAXN],st[MAXN],ans;
struct data{
    int id,val;
    data(int id=0,int val=0):id(id),val(val){}
    bool operator<(const data& t)const{
        return val<t.val || (val==t.val&&id<t.id);
    }
};
priority_queue<data> q01,q02,q12,q21;
void upd(int x){
    if(st[x]==0)q01.push(data(x,a[x])),q02.push(data(x,b[x]));
    else if(st[x]==1)q12.push(data(x,b[x]-a[x]));
    else if(st[x]==2)q21.push(data(x,a[x]-b[x]));
}

int main(){
    scanf("%d%d%d",&N,&P,&S);
    for(int i=1;i<=N;++i)scanf("%d",&a[i]),q01.push(data(i,a[i]));
    for(int i=1;i<=N;++i)scanf("%d",&b[i]),q02.push(data(i,b[i]));
    while(P||S){
        int delta=-INF,op=0;
        while(!q01.empty() && st[q01.top().id]!=0)q01.pop();
        while(!q02.empty() && st[q02.top().id]!=0)q02.pop();
        while(!q12.empty() && st[q12.top().id]!=1)q12.pop();
        while(!q21.empty() && st[q21.top().id]!=2)q21.pop();
        if(P){
            if(!q01.empty() && q01.top().val>delta)delta=q01.top().val,op=1;
            if(!q02.empty() && !q21.empty() && q02.top().val+q21.top().val>delta)delta=q02.top().val+q21.top().val,op=2;
        }
        if(S){
            if(!q02.empty() && q02.top().val>delta)delta=q02.top().val,op=3;
            if(!q01.empty() && !q12.empty() && q01.top().val+q12.top().val>delta)delta=q01.top().val+q12.top().val,op=4;
        }
        ans+=delta;
        if(op==1){
            int id=q01.top().id;
            st[id]=1,upd(id),--P;
        }else if(op==2){
            int id1=q02.top().id,id2=q21.top().id;
            st[id1]=2,upd(id1),st[id2]=1,upd(id2),--P;
        }else if(op==3){
            int id=q02.top().id;
            st[id]=2,upd(id),--S;
        }else{
            int id1=q01.top().id,id2=q12.top().id;
            st[id1]=1,upd(id1),st[id2]=2,upd(id2),--S;
        }
    }
    printf("%d\n",ans);
    for(int i=1;i<=N;++i)if(st[i]==1)printf("%d ",i);putchar('\n');
    for(int i=1;i<=N;++i)if(st[i]==2)printf("%d ",i);putchar('\n');
    return 0;
}