【BZOJ4977】[Lydsy1708月赛] 跳伞求生（模拟费用流）

点此看题面

大致题意： 有\(n\)个队友，每人有\(a_i\)发弹药。有\(m\)个敌人，每人有\(b_i\)发弹药，且击杀他可以得到\(v_i\)点积分。已知每个队友（设其为\(i\)）最多选择一个敌人（设其为\(j\)，每个敌人只能被选择一次），若\(a_i>b_j\)，则得到\(a_i-b_j+v_j\)点积分。求最大积分。

模拟费用流

这是模拟费用流的一道基础题。

考虑先将所有人按照弹药数量排序（弹药数量相同时，队友在前，敌人在后），然后依次枚举每一个人，则每个队友必然能够且只能够与之前的敌人产生贡献。

现在我们是在枚举\(i\)，而积分的计算式为\(a_i-b_j+v_j\)，\(a_i\)确定时，就是要找最大的\(-b_j+v_j\)，只要开个堆即可求出。

但是，如果你现在采取了最优策略，不一定就是全局的最优策略。

因此，模拟费用流有一个十分核心的退流（后悔）操作，即若\(a_i\)选择了一个敌人，就把选择的\(-b_j+v_j\)从堆中弹出（每个敌人只能被选择一次），再把\(-a_i\)加入堆中。

考虑这个东西的意义是什么，如果之后的一个\(a_k\)选中了\(-a_i\)，就说明我们决定把第\(i\)个队友赶走，并让第\(k\)个队友选择第\(i\)个队友原本选择的敌人。

或许你会像我一开始那样感到疑惑，为什么这里直接把第\(i\)个队友赶走，说不定第\(i\)个队友可以选择之前某个敌人使答案更大呢？

但仔细想想，每个队友其实是没有区别的，如果第\(i\)个队友能够选择之前的某个敌人使答案更大，那么\(a_k\)就不应该选中\(-a_i\)，而是选中那个敌人。

因此，第\(i\)个队友已经失去了作用，完全可以乱棍打死。

这道题就这样做完了。

代码

#include

#define Tp template

#define Ts template

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define N 100000

using namespace std;

int n,m;priority_queue q;

struct Data

{

int x,v;I bool operator < (Con Data& o) Con {return x^o.x?x

}s[2*N+5];

int main()

{

RI i;for(scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%d",&s[i].x),s[i].v=-1;

for(i=1;i<=m;++i) scanf("%d%d",&s[n+i].x,&s[n+i].v);sort(s+1,s+n+m+1);

long long ans=0;for(i=1;i<=n+m;++i) ~s[i].v?(q.push(-s[i].x+s[i].v),0)://敌人，加入堆中

!q.empty()&&s[i].x+q.top()>=0&&(ans+=s[i].x+q.top(),q.pop(),q.push(-s[i].x),0);//队友，如果能使答案变大就选择，并加入堆中

return printf("%lld\n",ans),0;//输出答案

}