【Atcoder思维训练】AT2672 [AGC018C] Coins

· · 题解

Preface

一道标准的模拟网络流（费用流）题目，蒟蒻第一次做反悔贪心。

Problem

有 x+y+z 个人，第 i 个人有 A_i 个金币，B_i 个银币，C_i 个铜币。 选出 x 个人获得其金币，选出 y 个人获得其银币，选出 z 个人获得其铜币，在不重复选某个人的情况下，最大化获得的币的总数。 x+y+z\leq 10^5

Solution

其实看到这种有后效性的决策题目的时候我们首先想到的应该是网络流，比如像这道题，我们就可以立刻建出一个费用流模型，但是这道题的数据范围很鬼畜，很明显朴素的费用流是跑不过去的。

这个时候我们就不得不仔细思考一下费用流的本质了，对于一个分配完毕的网络，费用流可以通过若干次推流操作来增大收益，这个推流的过程实际上就是对物品进行重分配。

那我们就有一个问题了，既然费用流要在图上跑很久才能出结果，我们能不能直接模拟物品重分配来减小复杂度呢？根据题意，我们的重分配方案一共五种： 

a->b b->c c->a  
a->c c->b b->a  
a->c c->a  
a->b b->a  
b->c c->b

其中三个字母分别代表不同币种。
其中 -> 表示一个原本用在一个币种的人转换到另外一个币种，很显然这些人对空间是本质相同的，所以我们可以分别选择最优的人进行求解。

举个例子，上文中第一行重分配方式，我们就可以先选择从金币到银币贡献最大者，然后选择银币到铜币贡献最大者，最后选择铜币到金币贡献最大者。

然后我们发现这个过程其实可以用六个堆进行模拟，直到无流可退我们就结束计算。

最后我们还有一个疑问：上述的过程叫反悔贪心，但是普通费用流复杂度为 O(nmf)，反悔贪心能减少多少的复杂度，可以降低到通过的级别吗？

这就不得不说反悔的具体次数了，很显然我们将反悔一次的复杂度降为了 O(\log n)，那么只要反悔次数是线性级别我们就可以通过本题，我们分类讨论一下，两个元素相互交换的反悔显然每次会将两个乱序的元素重排，最多执行总人数次。三个元素互相交换的反悔的情况下同样会将三个乱序元素进行重排，同理。
code： 

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,x,y,z,sum;
int a[N],b[N],c[N];int st[N];
struct node{
    int id,data;
    bool operator <(const node &a)const{
        return data<a.data;
    }
};
node nmax(node a,node b){
    if(a.data<b.data)return b;
    else return a;
}
priority_queue <node> Q[7];
//a->b b->c c->a
//a->c c->b b->a
//a->c c->a
//a->b b->a
//b->c c->b
int mo[N][7];
void update(int x){
    Q[st[x]*2-1].push((node){x,mo[x][st[x]*2-1]});
    Q[st[x]*2].push((node){x,mo[x][st[x]*2]});
}
void modify(int x){
    if(x==1||x==4)st[Q[1].top().id]=2;
    if(x==2||x==3)st[Q[2].top().id]=3;
    if(x==1||x==5)st[Q[4].top().id]=3;
    if(x==2||x==4)st[Q[3].top().id]=1;
    if(x==2||x==5)st[Q[6].top().id]=2;
    if(x==1||x==3)st[Q[5].top().id]=1;
    update(Q[1].top().id);update(Q[2].top().id);
    update(Q[3].top().id);update(Q[4].top().id);
    update(Q[5].top().id);update(Q[6].top().id);
}
signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>x>>y>>z;n=x+y+z;
    for(int i=1;i<=x;i++){
        cin>>a[i]>>b[i]>>c[i];st[i]=1;sum+=a[i];
        Q[1].push((node){i,b[i]-a[i]});Q[2].push((node){i,c[i]-a[i]});
    }
    for(int i=x+1;i<=x+y;i++){
        cin>>a[i]>>b[i]>>c[i];st[i]=2;sum+=b[i];
        Q[3].push((node){i,a[i]-b[i]});Q[4].push((node){i,c[i]-b[i]});
    }
    for(int i=x+y+1;i<=x+y+z;i++){
        cin>>a[i]>>b[i]>>c[i];st[i]=3;sum+=c[i];
        Q[5].push((node){i,a[i]-c[i]});Q[6].push((node){i,b[i]-c[i]});
    }
    for(int i=1;i<=n;i++){
        mo[i][1]=b[i]-a[i];mo[i][2]=c[i]-a[i];
        mo[i][3]=a[i]-b[i];mo[i][4]=c[i]-b[i];
        mo[i][5]=a[i]-c[i];mo[i][6]=b[i]-c[i];
    }
    while(true){
        //a->b b->c c->a
        //a->c c->b b->a
        //a->c c->a
        //a->b b->a
        //b->c c->b
        int ab=-1e18;int ac=-1e18;int ba=-1e18;
        int bc=-1e18;int ca=-1e18;int cb=-1e18;
        for(int i=1;i<=6;i++){
            while(!Q[i].empty()&&st[Q[i].top().id]!=((i+1)/2))
                Q[i].pop();
        }
        if(!Q[1].empty())ab=Q[1].top().data;
        if(!Q[2].empty())ac=Q[2].top().data;
        if(!Q[3].empty())ba=Q[3].top().data;
        if(!Q[4].empty())bc=Q[4].top().data;
        if(!Q[5].empty())ca=Q[5].top().data;
        if(!Q[6].empty())cb=Q[6].top().data;
        node res=nmax(nmax(nmax(nmax((node){4,ab+ba},(node){5,bc+cb})
        ,(node){3,ac+ca}),(node){2,ac+cb+ba}),(node){1,ab+bc+ca});
        if(res.data<=0)break;sum+=res.data;modify(res.id);
    }
    cout<<sum;
}