模拟费用流 & 可撤销贪心

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 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include <string>
#include 
#include 
#include 
#include 
#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<using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



const int N = 1e6+10;
int n, x, y;
int a[N], b[N], va[N], vb[N];
pii s[5];
priority_queue q[5];
ll ans;

pii get(priority_queue &q, int *v1, int *v2) {
    while (q.size()&&(v1[q.top().y]||v2[q.top().y])) q.pop();
    return q.empty()?pii(-INF,0):q.top();
}
void add(int u, int tp) {
    if (va[u]) ans-=a[u],va[u]=0,++x;
    if (vb[u]) ans-=b[u],vb[u]=0,++y;
    if (tp==1) ans+=a[u],va[u]=1,--x,q[4].push(pii(b[u]-a[u],u));
    else ans+=b[u],vb[u]=1,--y,q[3].push(pii(a[u]-b[u],u));
}

int main() {
    scanf("%d%d%d", &n, &x, &y);
    REP(i,1,n) scanf("%d",a+i);
    REP(i,1,n) scanf("%d",b+i);
    REP(i,1,n) { 
        q[1].push(pii(a[i],i));
        q[2].push(pii(b[i],i));
    }
    int tot = x+y;
    REP(i,1,tot) {
        s[1] = get(q[1],va,vb);
        s[2] = get(q[2],va,vb);
        s[3] = get(q[3],va,va);
        s[4] = get(q[4],vb,vb);
        s[3].x += s[2].x;
        s[4].x += s[1].x;
        if (!x) s[1].x=s[3].x=-INF;
        if (!y) s[2].x=s[4].x=-INF;
        int p = max_element(s+1,s+5)-s;
        if (p==1) add(s[1].y,1);
        else if (p==2) add(s[2].y,2);
        else if (p==3) add(s[3].y,1),add(s[2].y,2);
        else add(s[4].y,2),add(s[1].y,1);
    }
    printf("%lld\n", ans);
    REP(i,1,n) if (va[i]) printf("%d ",i);hr;
    REP(i,1,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 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include <string>
#include 
#include 
#include 
#include 
#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<using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



#ifdef ONLINE_JUDGE
const int N = 1e6+10;
#else
const int N = 567;
#endif

int n, k, l, a[N], b[N];
int va[N], vb[N];
priority_queue q[10];
struct t3 {int x,a,b;} f[10];
ll ans;
pii s[10];
int cost(int x, int y) {
    int ret = 0;
    if (x!=y) {
        if (vb[x]) ++ret; else --ret;
        if (va[y]) ++ret; else --ret;
    }
    return ret<0?-1:ret>0?1:0;
}
void add(int x, int y) {
    l += cost(x,y);
    ans += a[x]+b[y];
    va[x] = vb[y] = 1;
    if (!vb[x]) q[4].push(pii(b[x],x));
    if (!va[y]) q[3].push(pii(a[y],y));
}
pii get(priority_queue &q, int *v1, int *v2) {
    while (q.size()&&(v1[q.top().y]||v2[q.top().y])) q.pop();
    return q.empty()?pii(-INF,0):q.top();
}
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        REP(i,0,4) while (q[i].size()) q[i].pop();
        scanf("%d%d%d", &n, &k, &l);
        REP(i,1,n) scanf("%d",a+i);
        REP(i,1,n) scanf("%d",b+i);
        REP(i,1,n) {
            va[i] = vb[i] = 0;
            q[0].push(pii(a[i]+b[i],i));
            q[1].push(pii(a[i],i));
            q[2].push(pii(b[i],i));
        }
        l = k-l, ans = 0;
        REP(i,1,k) {
            s[0] = get(q[0],va,vb);
            s[1] = get(q[1],va,va);
            s[2] = get(q[2],vb,vb);
            s[3] = get(q[3],va,va);
            s[4] = get(q[4],vb,vb);
            f[0] = {s[1].x+s[2].x,s[1].y,s[2].y};
            f[1] = {s[0].x,s[0].y,s[0].y};
            f[2] = {s[1].x+s[4].x,s[1].y,s[4].y};
            f[3] = {s[2].x+s[3].x,s[3].y,s[2].y};
            if (l+cost(f[0].a,f[0].b)<0) f[0].x=-INF;
            int p = max_element(f,f+4,[](t3 a, t3 b){return a.xf;
            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 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include <string>
#include 
#include 
#include 
#include 
#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<using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



const int N = 1e6+50;
int n, k, a[N], b[N];
priority_queue<int,vector<int>,greater<int> > q[2];

int main() {
    scanf("%d%d", &n, &k);
    REP(i,1,n) scanf("%d", a+i);
    REP(i,1,n) scanf("%d", b+i);
    int l = 0, r = 2e9;
    ll ans = 0;
    while (l<=r) {
        REP(i,0,1) while (q[i].size()) q[i].pop();
        ll ret = 0;
        int cnt = 0, mid = (ll)l+r>>1;
        REP(i,1,n) {
            q[0].push(a[i]);
            ll t1 = q[0].top()+(ll)b[i]-mid;
            ll t2 = q[1].empty()?INF:b[i]+q[1].top();
            if (t1<=0&&t1<=t2) {
                ret += t1, ++cnt;
                q[1].push(-b[i]);
                q[0].pop();
            }
            else if (t2<0) {
                ret += t2;
                q[1].pop();
                q[1].push(-b[i]);
            }
        }
        if (cnt>=k) ans=ret+(ll)k*mid,r=mid-1;
        else l=mid+1;
    }
    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 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include <string>
#include 
#include 
#include 
#include 
#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<using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



const int N = 1e6+10;
int n, a[N], b[N];
int va[N], vb[N];
priority_queue q[3];
priority_queue,greater > qq[2]; 
pii s[4];
void add(int u, int tp) {
    if (tp==0) va[u]=1,q[1].push(pii(b[u],u)),qq[0].push(pii(a[u],u));
    else vb[u]=1,qq[1].push(pii(b[u],u));
}
void work() {
    scanf("%d", &n);
    REP(i,0,2) while (q[i].size()) q[i].pop();
    REP(i,0,1) while (qq[i].size()) qq[i].pop();
    REP(i,1,n) {
        scanf("%d%d",a+i,b+i);
        q[0].push(pii(a[i],i));
        q[2].push(pii(a[i]+b[i],i));
        va[i] = vb[i] = 0;
    }
    ll ans = 0;
    REP(i,1,2*n) {
        while (q[0].size()&&va[q[0].top().y]) q[0].pop();
        s[0] = q[0].empty()?pii(-INF,0):q[0].top();
        while (q[1].size()&&(!va[q[1].top().y]||vb[q[1].top().y])) q[1].pop();
        s[1] = q[1].empty()?pii(-INF,0):q[1].top();
        while (q[2].size()&&va[q[2].top().y]) q[2].pop();
        s[2] = s[3] = q[2].empty()?pii(-INF,0):q[2].top();
        if (i==1) s[2].x = s[3].x = -INF;
        else { 
            while (qq[0].size()&&(!va[qq[0].top().y]||vb[qq[0].top().y])) qq[0].pop();
            if (qq[0].size()) s[2].x -= qq[0].top().x;
            else s[2].x = -INF;
            while (qq[1].size()&&!vb[qq[1].top().y]) qq[1].pop();
            if (qq[1].size()) s[3].x -= qq[1].top().x;
            else s[3].x = -INF;
        }
        int p = max_element(s,s+4)-s;
        ans += s[p].x;
        if (p<=1) add(s[p].y,p);
        else { 
            //要注意先删除在添加, 不然qq会变
            if (p==2) va[qq[0].top().y]=0,q[0].push(qq[0].top());
            else vb[qq[1].top().y]=0,q[1].push(qq[1].top());
            add(s[p].y,0),add(s[p].y,1);
        }
        printf("%lld%c",ans," \n"[i==2*n]);
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) work();
}

其他-贪心图论-网络流

模拟费用流 & 可撤销贪心

相关

标签