[NOI2019]序列 [贪心,模拟费用流]

[NOI2019]序列 [贪心,模拟费用流]

​​传送门​​

首先你需要知道网络流的建图方法，偷一张图

我开始没有想到怎么限制 L 个相同，我们何不先选出 k 对，然后把 k 对拆开调整两边的最大选择

新建两个点 C，D 来给两边调整的空间

我们可以模拟这个网络流的运作过程

类似某些贪心的题，用堆来维护最大之类的

我们可以记录 CD 可以通过的流量 flow，如果 CD 有流量，我们就可以在两边分别选最大

如果没有，我们可以选一个A，保证B在对面出现，然后在对面随便选一个B

或者选一个B， 保证A在对面出现，然后随便选一个 A

或者选一对最大的 A，B

我们发现 堆需要维护以下东西

没有出现的 A， 没有出现的 B，出现了B没有出现的A， 出现了A没有出现的B，AB都没有出现的

然后就可以模拟了！

#include#define N 200050using namespace std;int read(){ int cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;} while(isdigit(ch)) cnt = (cnt << 1) + (cnt << 3) + (ch-'0'), ch = getchar(); return cnt * f;}typedef long long ll;int T, n, k, L, a[N], b[N];int sta[N], id[N];ll ans, Flow;struct A{ int id; bool operator < (const A &x) const{ return a[id] < a[x.id];} }tmp1;struct B{ int id; bool operator < (const B &x) const{ return b[id] < b[x.id];} }tmp2;struct AB{ int id; bool operator < (const AB &x) const{ return a[id] + b[id] < a[x.id] + b[x.id];} }tmp3;priority_queue q1, p1;priority_queue q2, p2;priority_queue q;bool cmpa(int x, int y){ return a[x] > a[y];}bool cmpb(int x, int y){ return b[x] > b[y];}void Init(){ while(!q1.empty()) q1.pop(); while(!p1.empty()) p1.pop(); while(!q2.empty()) q2.pop(); while(!p2.empty()) p2.pop(); while(!q.empty()) q.pop(); ans = Flow = 0; memset(sta, 0, sizeof(sta));}void Prework(int x){ for(int i=1; i<=n; i++) id[i] = i; sort(id+1, id+n+1, cmpa); for(int i=1; i<=x; i++) ans += a[id[i]], sta[id[i]] |= 1; sort(id+1, id+n+1, cmpb); for(int i=1; i<=x; i++) ans += b[id[i]], sta[id[i]] |= 2; }void Pop(){ while(!q1.empty() && sta[q1-().id] & 1) q1.pop(); while(!p1.empty() && sta[p1-().id] ^ 2) p1.pop(); while(!q2.empty() && sta[q2-().id] & 2) q2.pop(); while(!p2.empty() && sta[p2-().id] ^ 1) p2.pop(); while(!q.empty() && sta[q-().id]) q.pop(); }void Update1(){ // 任意选 int x = q1-().id, y = q2-().id; Flow--; ans += a[x] + b[y]; sta[x] |= 1; sta[y] |= 2; if(sta[x] == 1) tmp2.id = x, p2.push(tmp2); if(sta[y] == 2) tmp1.id = y, p1.push(tmp1); Flow += (x == y) ? 1 : ((sta[x] == 3) + (sta[y] == 3));}void Update2(){ int s1 = 0, s2 = 0, s3 = 0; if(!p1.empty()) s1 = a[p1-().id] + b[q2-().id]; if(!p2.empty()) s2 = a[q1-().id] + b[p2-().id]; if(!q.empty()) s3 = a[q-().id] + b[q-().id]; int mx = max(max(s1, s2), s3); ans += mx; if(s1 == mx){ int x = p1-().id, y = q2-().id; sta[x] |= 1; sta[y] |= 2; if(sta[y] == 3) Flow++; else tmp1.id = y, p1.push(tmp1); return; } if(s2 == mx){ int x = q1-().id, y = p2-().id; sta[x] |= 1; sta[y] |= 2; if(sta[x] == 3) Flow++; else tmp2.id = x, p2.push(tmp2); return; } if(s3 == mx){ int x = q-().id; sta[x] = 3;}}int main(){ T = read(); while(T--){ n = read(), k = read(), L = read(); for(int i=1; i<=n; i++) a[i] = read(); for(int i=1; i<=n; i++) b[i] = read(); Init(); Prework(k - L); for(int i=1; i<=n; i++){ tmp1.id = i; tmp2.id = i; tmp3.id = i; if(sta[i] == 0){ q1.push(tmp1); q2.push(tmp2); q.push(tmp3);} if(sta[i] == 1){ p2.push(tmp2); q2.push(tmp2);} if(sta[i] == 2){ p1.push(tmp1); q1.push(tmp1);} if(sta[i] == 3) Flow++; } while(L--){ Pop(); if(Flow) Update1(); else Update2(); } printf("%lld\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。