模拟费用流 & 可撤销贪心

1. CF730I Olympiad in Programming and Sports

大意: $n$个人, 第$i$个人编程能力$a_i$, 运动能力$b_i$, 要选出$p$个组成编程队, $s$个组成运动队, 每个队的收益为队员能力和, 求最大收益.

费用流做法很显然, 开两个点$X,Y$表示编程和运动, 源点向每个人连边, 代价为$0$, 每个人向$X$连边, 代价为编程能力, 每个人向$Y$连边, 代价为运动能力, $X$向汇点连边容量为$p$, $Y$向汇点连边, 容量为$s$, 然后求出最大费用最大流即为答案.

考虑用堆模拟费用流. 每次增广只有四种情况.

添加一个未被选择的人去编程队
添加一个未被选择的人去运动队
让一个人从运动队到编程队, 再选择一个未被选择的人去运动队
让一个人从编程队到运动队, 再选择一个未被选择的人去编程队

前两种情况直接用堆维护最大即可. 后两种情况的话, 在每次决策时, 都把替换的收益扔进一个堆里即可.

#include <iostream>

#include <sstream>

#include <algorithm>

#include <cstdio>

#include <cmath>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <cstring>

#include <bitset>

#include <functional>

#include <random>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define PER(i,a,n) for(int i=n;i>=a;--i)

#define hr putchar(10)

#define pb push_back

#define lc (o<<1)

#define rc (lc|1)

#define mid ((l+r)>>1)

#define ls lc,l,mid

#define rs rc,mid+1,r

#define x first

#define y second

#define io std::ios::sync_with_stdio(false)

#define endl '\n'

#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

const int P = 1e9+, INF = 0x3f3f3f3f;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll qpow(ll a,ll n) {ll r=%P;for (a%=P;n;a=a*a%P,n>>=)if(n&)r=r*a%P;return r;}

ll inv(ll x){return x<=?:inv(P%x)*(P-P/x)%P;}

inline int rd() {int x=;char p=getchar();while(p<''||p>'')p=getchar();while(p>=''&&p<='')x=x*+p-'',p=getchar();return x;}

//head

const int N = 1e6+;

int n, x, y;

int a[N], b[N], va[N], vb[N];

pii s[];

priority_queue<pii> q[];

ll ans;

pii get(priority_queue<pii> &q, int *v1, int *v2) {

    while (q.size()&&(v1[q.top().y]||v2[q.top().y])) q.pop();

    return q.empty()?pii(-INF,):q.top();

}

void add(int u, int tp) {

    if (va[u]) ans-=a[u],va[u]=,++x;

    if (vb[u]) ans-=b[u],vb[u]=,++y;

    if (tp==) ans+=a[u],va[u]=,--x,q[].push(pii(b[u]-a[u],u));

    else ans+=b[u],vb[u]=,--y,q[].push(pii(a[u]-b[u],u));

}

int main() {

    scanf("%d%d%d", &n, &x, &y);

    REP(i,,n) scanf("%d",a+i);

    REP(i,,n) scanf("%d",b+i);

    REP(i,,n) {

        q[].push(pii(a[i],i));

        q[].push(pii(b[i],i));

    }

    int tot = x+y;

    REP(i,,tot) {

        s[] = get(q[],va,vb);

        s[] = get(q[],va,vb);

        s[] = get(q[],va,va);

        s[] = get(q[],vb,vb);

        s[].x += s[].x;

        s[].x += s[].x;

        if (!x) s[].x=s[].x=-INF;

        if (!y) s[].x=s[].x=-INF;

        int p = max_element(s+,s+)-s;

        if (p==) add(s[].y,);

        else if (p==) add(s[].y,);

        else if (p==) add(s[].y,),add(s[].y,);

        else add(s[].y,),add(s[].y,);

    }

    printf("%lld\n", ans);

    REP(i,,n) if (va[i]) printf("%d ",i);hr;

    REP(i,,n) if (vb[i]) printf("%d ",i);hr;

}

2. NOI2019 序列

大意: 给定两个序列$a,b$, 要求每个序列选出$K$个元素, 且位置相同的元素要至少选$L$个, 求选出元素的最大和.

首先可以得到一个显然的费用流做法.

源点向$a$中每个元素连边, 代价为$a_i$, $b$中每个元素向汇点连边, 代价为$b_i$.

$a$中每个点向对应位置的$b$中的点连边.

再开两个点$X,Y$, $X$向$Y$连容量为$K-L$的边, 表示可以选出$K-L$个不一样的位置.

$a$中每个点再连向$X$, $Y$连向$b$中每个点.

最后求出源点到汇点容量为$K$的最大费用流即为答案.

考虑用堆模拟费用流, 分四种情况.

从$a$中选最大,$b$中也选最大 (要求X到Y仍有剩余流量)
$a$,$b$选出位置相同
$a$中选最大,$b$中选出之前选过的$a$对应位置
$b$中选最大,$a$中选出之前选过的$b$对应位置

#include <iostream>

#include <sstream>

#include <algorithm>

#include <cstdio>

#include <cmath>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <cstring>

#include <bitset>

#include <functional>

#include <random>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define PER(i,a,n) for(int i=n;i>=a;--i)

#define hr putchar(10)

#define pb push_back

#define lc (o<<1)

#define rc (lc|1)

#define mid ((l+r)>>1)

#define ls lc,l,mid

#define rs rc,mid+1,r

#define x first

#define y second

#define io std::ios::sync_with_stdio(false)

#define endl '\n'

#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

const int P = 1e9+, INF = 0x3f3f3f3f;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll qpow(ll a,ll n) {ll r=%P;for (a%=P;n;a=a*a%P,n>>=)if(n&)r=r*a%P;return r;}

ll inv(ll x){return x<=?:inv(P%x)*(P-P/x)%P;}

inline int rd() {int x=;char p=getchar();while(p<''||p>'')p=getchar();while(p>=''&&p<='')x=x*+p-'',p=getchar();return x;}

//head

#ifdef ONLINE_JUDGE

const int N = 1e6+;

#else

const int N = ;

#endif

int n, k, l, a[N], b[N];

int va[N], vb[N];

priority_queue<pii> q[];

struct t3 {int x,a,b;} f[];

ll ans;

pii s[];

int cost(int x, int y) {

    int ret = ;

    if (x!=y) {

        if (vb[x]) ++ret; else --ret;

        if (va[y]) ++ret; else --ret;

    }

    return ret<?-:ret>?:;

}

void add(int x, int y) {

    l += cost(x,y);

    ans += a[x]+b[y];

    va[x] = vb[y] = ;

    if (!vb[x]) q[].push(pii(b[x],x));

    if (!va[y]) q[].push(pii(a[y],y));

}

pii get(priority_queue<pii> &q, int *v1, int *v2) {

    while (q.size()&&(v1[q.top().y]||v2[q.top().y])) q.pop();

    return q.empty()?pii(-INF,):q.top();

}

int main() {

    int t;

    scanf("%d", &t);

    while (t--) {

        REP(i,,) while (q[i].size()) q[i].pop();

        scanf("%d%d%d", &n, &k, &l);

        REP(i,,n) scanf("%d",a+i);

        REP(i,,n) scanf("%d",b+i);

        REP(i,,n) {

            va[i] = vb[i] = ;

            q[].push(pii(a[i]+b[i],i));

            q[].push(pii(a[i],i));

            q[].push(pii(b[i],i));

        }

        l = k-l, ans = ;

        REP(i,,k) {

            s[] = get(q[],va,vb);

            s[] = get(q[],va,va);

            s[] = get(q[],vb,vb);

            s[] = get(q[],va,va);

            s[] = get(q[],vb,vb);

            f[] = {s[].x+s[].x,s[].y,s[].y};

            f[] = {s[].x,s[].y,s[].y};

            f[] = {s[].x+s[].x,s[].y,s[].y};

            f[] = {s[].x+s[].x,s[].y,s[].y};

            if (l+cost(f[].a,f[].b)<) f[].x=-INF;

            int p = max_element(f,f+,[](t3 a, t3 b){return a.x<b.x;})-f;

            add(f[p].a,f[p].b);

        }

        printf("%lld\n", ans);

    }

}

3. CF802O April Fools' Problem (hard)

大意: $n$道题, 第$i$天可以花费$a_i$准备一道题, 花费$b_i$打印一道题, 每天最多准备一道, 最多打印一道, 准备的题可以留到以后打印, 求最少花费使得准备并打印$k$道题.

这个题好有意思, 直接用堆很难模拟, 似乎可以用线段树来模拟. 一个非常好写的做法是带权二分,带权二分具体原理其实一直都没搞懂。。。

#include <iostream>

#include <sstream>

#include <algorithm>

#include <cstdio>

#include <cmath>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <cstring>

#include <bitset>

#include <functional>

#include <random>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define PER(i,a,n) for(int i=n;i>=a;--i)

#define hr putchar(10)

#define pb push_back

#define lc (o<<1)

#define rc (lc|1)

#define ls lc,l,mid

#define rs rc,mid+1,r

#define x first

#define y second

#define io std::ios::sync_with_stdio(false)

#define endl '\n'

#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

const int P = 1e9+, INF = 0x3f3f3f3f;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll qpow(ll a,ll n) {ll r=%P;for (a%=P;n;a=a*a%P,n>>=)if(n&)r=r*a%P;return r;}

ll inv(ll x){return x<=?:inv(P%x)*(P-P/x)%P;}

inline int rd() {int x=;char p=getchar();while(p<''||p>'')p=getchar();while(p>=''&&p<='')x=x*+p-'',p=getchar();return x;}

//head

const int N = 1e6+;

int n, k, a[N], b[N];

priority_queue<int,vector<int>,greater<int> > q[];

int main() {

    scanf("%d%d", &n, &k);

    REP(i,,n) scanf("%d", a+i);

    REP(i,,n) scanf("%d", b+i);

    int l = , r = 2e9;

    ll ans = ;

    while (l<=r) {

        REP(i,,) while (q[i].size()) q[i].pop();

        ll ret = ;

        int cnt = , mid = (ll)l+r>>;

        REP(i,,n) {

            q[].push(a[i]);

            ll t1 = q[].top()+(ll)b[i]-mid;

            ll t2 = q[].empty()?INF:b[i]+q[].top();

            if (t1<=&&t1<=t2) {

                ret += t1, ++cnt;

                q[].push(-b[i]);

                q[].pop();

            }

            else if (t2<) {

                ret += t2;

                q[].pop();

                q[].push(-b[i]);

            }

        }

        if (cnt>=k) ans=ret+(ll)k*mid,r=mid-;

        else l=mid+;

    }

    printf("%lld\n", ans);

}

4. hdu 6698 Coins

大意: $n$组硬币, 第$i$组有一个$a_i$元的和$b_i$元的, 每组要么不选, 要么选$a_i$, 要么全选, 对于$k\le 2n$, 求出拿$k$个硬币的最大钱数.

堆模拟这四种方案即可:

取一个最大的$a$
补上一个最大的$b$
删掉一个$a$, 取一个最大的$a+b$
删掉一个$b$, 取一个最大的$a+b$

#include <iostream>

#include <sstream>

#include <algorithm>

#include <cstdio>

#include <cmath>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <cstring>

#include <bitset>

#include <functional>

#include <random>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define PER(i,a,n) for(int i=n;i>=a;--i)

#define hr putchar(10)

#define pb push_back

#define lc (o<<1)

#define rc (lc|1)

#define mid ((l+r)>>1)

#define ls lc,l,mid

#define rs rc,mid+1,r

#define x first

#define y second

#define io std::ios::sync_with_stdio(false)

#define endl '\n'

#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

const int P = 1e9+, INF = 0x3f3f3f3f;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll qpow(ll a,ll n) {ll r=%P;for (a%=P;n;a=a*a%P,n>>=)if(n&)r=r*a%P;return r;}

ll inv(ll x){return x<=?:inv(P%x)*(P-P/x)%P;}

inline int rd() {int x=;char p=getchar();while(p<''||p>'')p=getchar();while(p>=''&&p<='')x=x*+p-'',p=getchar();return x;}

//head

const int N = 1e6+;

int n, a[N], b[N];

int va[N], vb[N];

priority_queue<pii> q[];

priority_queue<pii,vector<pii>,greater<pii> > qq[];

pii s[];

void add(int u, int tp) {

    if (tp==) va[u]=,q[].push(pii(b[u],u)),qq[].push(pii(a[u],u));

    else vb[u]=,qq[].push(pii(b[u],u));

}

void work() {

    scanf("%d", &n);

    REP(i,,) while (q[i].size()) q[i].pop();

    REP(i,,) while (qq[i].size()) qq[i].pop();

    REP(i,,n) {

        scanf("%d%d",a+i,b+i);

        q[].push(pii(a[i],i));

        q[].push(pii(a[i]+b[i],i));

        va[i] = vb[i] = ;

    }

    ll ans = ;

    REP(i,,*n) {

        while (q[].size()&&va[q[].top().y]) q[].pop();

        s[] = q[].empty()?pii(-INF,):q[].top();

        while (q[].size()&&(!va[q[].top().y]||vb[q[].top().y])) q[].pop();

        s[] = q[].empty()?pii(-INF,):q[].top();

        while (q[].size()&&va[q[].top().y]) q[].pop();

        s[] = s[] = q[].empty()?pii(-INF,):q[].top();

        if (i==) s[].x = s[].x = -INF;

        else {

            while (qq[].size()&&(!va[qq[].top().y]||vb[qq[].top().y])) qq[].pop();

            if (qq[].size()) s[].x -= qq[].top().x;

            else s[].x = -INF;

            while (qq[].size()&&!vb[qq[].top().y]) qq[].pop();

            if (qq[].size()) s[].x -= qq[].top().x;

            else s[].x = -INF;

        }

        int p = max_element(s,s+)-s;

        ans += s[p].x;

        if (p<=) add(s[p].y,p);

        else {

            //要注意先删除在添加, 不然qq会变

            if (p==) va[qq[].top().y]=,q[].push(qq[].top());

            else vb[qq[].top().y]=,q[].push(qq[].top());

            add(s[p].y,),add(s[p].y,);

        }

        printf("%lld%c",ans," \n"[i==*n]);

    }

}

int main() {

    int t;

    scanf("%d", &t);

    while (t--) work();

}

模拟费用流 & 可撤销贪心的更多相关文章

[NOI2019]序列（模拟费用流）
题意: 有两个长度为n的序列,要求从每个序列中选k个,并且满足至少有l个位置都被选,问总和最大是多少. $1\leq l\leq k\leq n\leq 2*10^5$. 首先,记录当前考虑到的位 ...
UOJ &num;455 [UER &num;8]雪灾与外卖 (贪心、模拟费用流)
题目链接 http://uoj.ac/contest/47/problem/455 题解模拟费用流,一个非常神奇的东西. 本题即为WC2019 laofu的讲课中的Problem 8,经典的老鼠进洞 ...
luogu P5470 [NOI2019]序列 dp 贪心费用流模拟费用流
LINK:序列考虑前20分容易想到爆搜. 考虑dp 容易设$f_{i,j,k,l}$表示前i个位置选了j对且此时A选择了k个 B选择了l个的最大值.期望得分28. code //#incl ...
贪心（模拟费用流）：NOIP2011 观光公交
[问题描述] 风景迷人的小城Y 市,拥有n 个美丽的景点.由于慕名而来的游客越来越多,Y 市特意安排了一辆观光公交车,为游客提供更便捷的交通服务.观光公交车在第0 分钟出现在1号景点,随后依次前往2. ...
BZOJ4977[Lydsy1708月赛]跳伞求生——贪心+堆+模拟费用流
题目链接: 跳伞求生可以将题目转化成数轴上有$n$个人和$m$个房子,坐标分别为$a_{i}$和$b_{i}$,每个人可以进一个他左边的房子,每个房子只能进一个人.每个房子有一个收益$c_{i}$, ...
【BZOJ3502/2288】PA2012 Tanie linie/【POJ Challenge】生日礼物堆+链表（模拟费用流）
[BZOJ3502]PA2012 Tanie linie Description n个数字,求不相交的总和最大的最多k个连续子序列. 1<= k<= N<= 1000000. Sam ...
【bzoj1150】[CTSC2007]数据备份Backup 模拟费用流+链表+堆
题目描述你在一家 IT 公司为大型写字楼或办公楼(offices)的计算机数据做备份.然而数据备份的工作是枯燥乏味的,因此你想设计一个系统让不同的办公楼彼此之间互相备份,而你则坐在家中尽享计算机游戏 ...
[UOJ455][UER &num;8]雪灾与外卖——堆+模拟费用流
题目链接: [UOJ455]雪灾与外卖题目描述:有$n$个送餐员(坐标为$x_{i}$)及$m$个餐厅(坐标为$y_{i}$,权值为$w_{i}$),每个送餐员需要前往一个餐厅,每个餐厅只能容纳$c ...
Codeforces 280D k-Maximum Subsequence Sum [模拟费用流，线段树]
洛谷 Codeforces bzoj1,bzoj2 这可真是一道n倍经验题呢-- 思路我首先想到了DP,然后矩阵,然后线段树,然后T飞-- 搜了题解之后发现是模拟费用流. 直接维护选k个子段时的最优 ...

随机推荐

深入解析js异步编程利器Generator
我们在编写Nodejs程序时,经常会用到回调函数,在一个操作执行完成之后对返回的数据进行处理,我简单的理解它为异步编程. 如果操作很多,那么回调的嵌套就会必不可少,那么如果操作非常多,那么回调的嵌套就 ...
[刘阳Java]&lowbar;避开环境配置快速的使用Java的开发工具&lowbar;第5讲
我们一般学习Java都应该遵循通过系统的命令工具来编译Java程序,然后对编译好Java程序进行运行,这个是非常好的习惯.但是随着后期学习Java技术的深入我们也得像Java的IDE工具屈服.所以,可 ...
C++文件输入输出
#include <iostream> //有些系统里面可以省略此头文件 #include <fstream> #include <string> int main ...
查询SQL 对象及存储过程
select * from database..sysobjects order by name EXEC Sp_HelpText 'Proc_Export268';
开放平台-web实现QQ第三方登录
应用场景 web应用通过QQ登录授权实现第三方登录. 操作步骤 1 注册成为QQ互联平台开发者,http://connect.qq.com/ 2 准备一个可访问的域名, ...
&lowbar;&lowbar;dict&lowbar;&lowbar;和&lowbar;&lowbar;slots&lowbar;&lowbar;
__dict__: __slots__:
C&num;中DllImport用法和路径问题
DllImport是System.Runtime.InteropServices命名空间下的一个属性类,其功能是提供从非托管DLL导出的函数的必要调用信息. DllImport属性应用于方法,要 ...
Qt 多线程学习
最近的项目上用到了关于多线程的知识,自己也比较感兴趣,所以就拿了那本<C++ GUI Qt4 编程>来学习. 这本书的第14章是关于多线程的知识,使用的Qt版本是Qt4.x.在下用的是最新 ...
php使用openssl进行Rsa长数据加密,解密保存问题
原来代码: public function encrypt($data) { if (openssl_public_encrypt(base64_encode($data), $encrypted, ...
Microsoft dotnetConf 2015
Microsoft dotnetConf 2015 一些整理 dotnetConf 2015 直播计划: 第一天 (10 个主讲) - .NET Product Teams 主讲人为 .NET 产 ...