模拟费用流

　　在数轴（树）上有若干白点与若干黑点，要求按题意对它们进行匹配。

一、小清新模拟费用流。（4849: [Neerc2016]Mole Tunnels）

　　题意：一颗高为 log（n）的树。首先每个节点上有若干白点，然后每一个时刻在某一节点上激活一个黑点。黑点与白点匹配的代价为两点距离。求每一时刻被激活的黑点都得到匹配的最小代价。

　　sol：这是一道很清新的模拟费用流问题。按照费用流的做法（先找代价最小的流，然后再流掉这些流）。具体而言：我们对于每一个节点记录它到达它的子树中最近的一个白点的距离，以及其所在节点。当一个黑点被激活时，我们枚举它的所有祖先（即与匹配点的lca），同时也记录它到这个祖先节点的距离。在向上跳的同时更新最佳的匹配白点。然后再模拟流的变化。

#include<bits/stdc++.h>
using namespace std;
int read()
{
    int x=0,f=1;    char ch=getchar();
    while(ch<'0'||ch>'9')    {if(ch=='-')    f=-1;    ch=getchar();}
    while(ch>='0'&&ch<='9')    {x=(x<<3)+(x<<1)+(ch^48);    ch=getchar();}
    return x*f;
}
int n,m,ans;
int head[100050],nex[100050],ver[100050],tot;
int sum[100050],flow[100050],dis[100050],pos[100050];
void update(int u)
{
    dis[u]=100;
    if(sum[u])    dis[u]=0,pos[u]=u;
    else
    {
        for(int i=head[u];i;i=nex[i])
        {
            int v=ver[i];
            int DIS=dis[v]+(flow[v]>=0? 1:-1);
            if(dis[u]>DIS)    dis[u]=DIS,pos[u]=pos[v];
        }
    }
}
int main()
{
    n=read();    m=read();
    for(int i=1;i<=n;++i)
    {
        sum[i]=read();
        ++tot;nex[tot]=head[i>>1];ver[tot]=i;head[i>>1]=tot;
    }
    for(int i=n;i>=1;--i)    update(i);
    while(m--)
    {
        int x,y,z,lca,X,Y,DIS;    z=x=read();    X=0;    DIS=100;
        while(z)
        {
            Y=dis[z];
            if(X+Y<DIS)    DIS=X+Y,y=pos[z],lca=z;
            X+=(flow[z]<=0? 1:-1);    z>>=1;
        }
        ans+=DIS;    sum[y]--;
        while(x!=lca)    update(x),flow[x]--,x>>=1;
        while(y!=lca)    update(y),flow[y]++,y>>=1;
        while(lca)    update(lca),lca>>=1;
        printf("%d ",ans);
    }
    return 0;
}

二、基础（4977: [[Lydsy1708月赛]跳伞求生）

　　题意：黑点与白点都有V值，而且每个白点有附带权值W。黑点x能匹配白点y当且仅当Vx>Vy，且它们匹配将产生Vx-Vy+Wy的贡献。求能产生的最大总贡献值（黑点不必全部得到匹配）。

　　sol：由于匹配限制，我们只需要维护一个关于白点的堆（用于撤销关于白点的不够优秀的匹配）。操作姿势是按照V值由小至大考虑所有的点。

　　关于此处堆的描述：当枚举到了一个点时，所有它之前的白点都将有一个代表元素在堆中。它们按照是否匹配黑点可分为两类。但是即使已经匹配了黑点也是有可能因为之后的黑点而更换匹配对象的，这是它们都在堆中的必要性。最为关键的是它们在堆中的关键值，这将是重要的讨论对象。易知关键值需要考虑的是此白点已经产生的贡献（匹配时的全额贡献）与将来会产生的贡献（匹配时的仅关于该点的贡献）。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int read()
{
    int x=0,f=1;    char ch=getchar();
    while(ch<'0'||ch>'9')    {if(ch=='-')    f=-1;    ch=getchar();}
    while(ch>='0'&&ch<='9')    {x=(x<<3)+(x<<1)+(ch^48);    ch=getchar();}
    return x*f;
}
int n,m,tot;    ll ans;
struct node
{
    int opt,pos,val;
    bool operator <(const node & o)const
    {
        if(pos!=o.pos)    return pos<o.pos;
        return opt<o.opt;
    }
}num[200050];
priority_queue<int >q;
int main()
{
    n=read();    m=read();
    for(int i=1;i<=n;++i)
    {
        ++tot;
        num[tot].pos=read();
        num[tot].val=num[tot].pos;
    }
    for(int i=1;i<=m;++i)
    {
        num[++tot].opt=1;
        num[tot].pos=read();
        num[tot].val=read()-num[tot].pos;
    }
    sort(num+1,num+tot+1);
    for(int i=1;i<=tot;++i)
        if(num[i].opt)    q.push(num[i].val);
        else
        {
            if(q.empty()||num[i].val+q.top()<=0)    continue;
            else
            {
                ans+=num[i].val+q.top();
                q.pop();    q.push(-num[i].val);
            }
        }
    printf("%lld",ans);
    return 0;
}

 三、升级（#455. 【UER #8】雪灾与外卖）

　　题目：黑点与白点都有V值，而且每个白点有附带权值W以及重数C。黑点x与白点y匹配没有限制，且代价为|Vx-Vy|+Wy。求每个黑点都得到匹配的最小代价。

　　sol：对于一对匹配，可能黑点在前白点在后也有可能白点在前黑点在后，我们在枚举到后面的点时考虑这对匹配。具体而言，当我们枚举到一个点时，考虑它与它之前的反色点的匹配。我们需要分别建关于白点的堆和关于黑点的堆，以此维护撤销代价。关于重数问题，我们只需要将堆中元素的类型换成pair即可。

#include<bits/stdc++.h>
#define ll long long
#define p pair<int ,int > 
#define mp make_pair
#define inf 1e9+5
using namespace std;
int read()
{
    int x=0,f=1;    char ch=getchar();
    while(ch<'0'||ch>'9')    {if(ch=='-')    f=-1;    ch=getchar();}
    while(ch>='0'&&ch<='9')    {x=(x<<3)+(x<<1)+(ch^48);    ch=getchar();}
    return x*f;
}
int n,m,tot;    ll ans;
int x[100050],y[100050],w[100050],c[100050];
priority_queue<p,vector<p>,greater<p> >X,Y;
p tmp;
void push_x(int x)
{
    int y;
    if(Y.empty())    y=inf;
    else
    {
        tmp=Y.top();    Y.pop();
        y=tmp.first;    tmp.second--;
        if(tmp.second)    Y.push(tmp);
    }
    ans+=x+y;
    X.push(mp(-(x+y)-x,1));
}
void push_y(int y,int w,int c)
{
    int s=0,x;
    while(s<c&&!X.empty()&&y+w+X.top().first<0)
    {
        tmp=X.top();    X.pop();    x=tmp.first;
        int sum=min(c-s,tmp.second);
        tmp.second-=sum;    s+=sum;
        if(tmp.second)    X.push(tmp);
        ans+=(ll)(y+w+x)*sum;
        Y.push(mp(-(y+w+x)-y+w,sum));
    }
    if(s)    X.push(mp(-(y+w),s));
    if(c-s)    Y.push(mp(-y+w,c-s));
}
int main()
{
    n=read();    m=read();    x[n+1]=y[m+1]=inf;
    for(int i=1;i<=n;++i)    x[i]=read();
    for(int i=1;i<=m;++i)    y[i]=read(),w[i]=read(),c[i]=read();
    for(int i=1;i<=m;++i)    tot=min(tot+c[i],n);
    if(tot<n){    printf("-1");return 0;}
    int a=1,b=1;
    while(a<=n||b<=m)
    {
        if(x[a]<y[b])    push_x(x[a]),a++;
        else    push_y(y[b],w[b],c[b]),b++;
    }
    printf("%lld",ans);
    return 0;
}

四、进阶（「ICPC World Finals 2018」征服世界）

　　题意：在树上有若干黑点与白点。黑点与白点的匹配代价为它们的距离。求每个黑点都得到匹配的最小代价。

　　sol：此题依旧可以按照上一题的方法处理，我们只需将堆换为可并堆即可。

#include<bits/stdc++.h>
#define ll long long
#define inf 3e11
#define ls son[u][0]
#define rs son[u][1]
using namespace std;
int read()
{
    int x=0,f=1;    char ch=getchar();
    while(ch<'0'||ch>'9')    {if(ch=='-')    f=-1;    ch=getchar();}
    while(ch>='0'&&ch<='9')    {x=(x<<3)+(x<<1)+(ch^48);    ch=getchar();}
    return x*f;
}
int n,x,y,z; ll ans;
int X[1000050],Y[1000050];
int head[1000050],nex[1000050],ver[1000050],edg[1000050],tot;
int rx[1000050],ry[1000050],son[30000050][2],dis[30000050],cnt;
ll val[30000050],sum[30000050];
int merge(int u,int v)
{
    if(!u||!v)    return u|v;
    if(val[u]>val[v])    swap(u,v);
    rs=merge(rs,v);
    if(dis[ls]<dis[rs])    swap(ls,rs);
    dis[u]=dis[rs]+1;
    return u;
}
void push(int &u,ll v,int s)
{
    ++cnt;    val[cnt]=v;    sum[cnt]=s;
    u=merge(u,cnt);
}
void calc(int &u,int &v,ll dis)
{
    while(u&&v)
    {
        ll vu=val[u];
        ll vv=val[v];
        if(vu+vv-dis>=0)    break;
        ll VAL=vu+vv-dis;
        int SUM=min(sum[u],sum[v]);
        if(!(sum[u]-=SUM))    u=merge(son[u][0],son[u][1]);
        if(!(sum[v]-=SUM))    v=merge(son[v][0],son[v][1]);
        ans+=VAL*SUM;
        push(u,-vv+dis,SUM);
        push(v,-vu+dis,SUM);
    }
}
void dfs(int u,int anc,ll dis)
{
    if(X[u])    push(rx[u],dis,X[u]);
    if(Y[u])    push(ry[u],dis-inf,Y[u]),ans+=(ll)inf*Y[u];
    for(int i=head[u];i;i=nex[i])
    {
        int v=ver[i];
        if(v==anc)    continue;
        dfs(v,u,dis+edg[i]);
        rx[u]=merge(rx[u],rx[v]);
        ry[u]=merge(ry[u],ry[v]);
    }
    calc(rx[u],ry[u],dis<<1);
}
int main()
{
    n=read();
    for(int i=1;i<n;++i)
    {
        x=read();    y=read();    z=read();
        ++tot;nex[tot]=head[x];ver[tot]=y;edg[tot]=z;head[x]=tot;
        ++tot;nex[tot]=head[y];ver[tot]=x;edg[tot]=z;head[y]=tot;
    }
    for(int i=1;i<=n;++i)
    {
        X[i]=read();    Y[i]=read();
        int tmp=min(X[i],Y[i]);
        X[i]-=tmp;    Y[i]-=tmp;
    }
    dfs(1,0,0);
    printf("%lld",ans);
    return 0;
}

五、毒瘤（P3826 [NOI2017]蔬菜）

　　题意：balabala......

　　sol：此题有两个毒瘤 First blood 和 Decline with each passing day 。

首先考虑最老实的暴力......（鬼才会去写）。因为此题有严重到后效性，所以很难从正面入手。顺着时间轴，发现蔬菜的数量在递减，然而如果逆着时间轴看的话，它反而是递增的。显然这种状态是易于解决的。于是我们便可以求出最后一天的状态，然后递推出之前的状态。如此，第一个毒瘤也只需要特判即可。

//费用流（暴力）
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int read()
{
    int x=0,f=1;    char ch=getchar();
    while(ch<'0'||ch>'9')    {if(ch=='-')    f=-1;    ch=getchar();}
    while(ch>='0'&&ch<='9')    {x=(x<<3)+(x<<1)+(ch^48);    ch=getchar();}
    return x*f;
}
int n,m,k,M,FLOW,S,T;
ll ANS,ans[100050];
int v[100050],f[100050],s[100050],d[100050];
int num[1050][1050],day[1050],cnt;
int head[1000050],nex[1000050],ver[1000050],val[10000050],flow[10000050],tot=1;
int dis[1000050],nar[1000050],vis[1000050],pre[1000050];
queue<int >q;
void add(int x,int y,int v,int f)
{
    ++tot;nex[tot]=head[x];ver[tot]=y;val[tot]=v;flow[tot]=f;head[x]=tot;
    ++tot;nex[tot]=head[y];ver[tot]=x;val[tot]=-v;flow[tot]=0;head[y]=tot;
}
bool spfa()
{
    for(int i=0;i<=cnt;++i)
        dis[i]=-1<<30,nar[i]=vis[i]=0;
    q.push(S);    dis[S]=0;    nar[S]=1<<30;    vis[S]=true;
    while(!q.empty())
    {
        int u=q.front();    q.pop();    vis[u]=false;
        for(int i=head[u];i;i=nex[i])
        {
            int v=ver[i];
            if(flow[i]&&dis[v]<dis[u]+val[i])
            {
                nar[v]=min(nar[u],flow[i]);
                dis[v]=dis[u]+val[i];
                pre[v]=i;
                if(!vis[v])
                {
                    vis[v]=true;
                    q.push(v);
                }
            }
        }
    }
    return dis[T]!=dis[0];
}
void calc()
{
    FLOW+=nar[T];
    ANS+=(ll)nar[T]*dis[T];
    int tmp=T;
    while(tmp!=S)
    {
        flow[pre[tmp]]-=nar[T];
        flow[pre[tmp]^1]+=nar[T];
        tmp=ver[pre[tmp]^1];
    }
}
void calc_aft(int tim)
{
    for(int i=1;i<=n;++i)
    {
        s[i]-=d[i];
        if(s[i]<=0)    continue;
        num[i][tim]=++cnt;
        add(num[i][tim-1],num[i][tim],0,s[i]);
    }
}
void calc_pre(int tim)
{
    if(tim>1)    calc_aft(tim);
    day[tim]=++cnt;    add(day[tim],T,0,m);
    for(int i=1;i<=n;++i)
        if(num[i][tim])    add(num[i][tim],day[tim],v[i],m);
    ++tim;
}
int main()
{
    n=read();    m=read();    k=read();    S=++cnt;    T=++cnt;
    for(int i=1;i<=n;++i)    v[i]=read(),f[i]=read(),s[i]=read(),d[i]=read();
    for(int i=1;i<=n;++i)    num[i][1]=++cnt,add(S,cnt,f[i],1),add(S,cnt,0,s[i]-1);
    for(int i=1;i<=1000;++i)
    {
        calc_pre(i);
        while(spfa())    calc();
        ans[i]=ANS;
    }
    while(k--)    printf("%lld
",ans[read()]);
    return 0;
}

#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
using namespace std;
int read()
{
    int x=0,f=1;    char ch=getchar();
    while(ch<'0'||ch>'9')    {if(ch=='-')    f=-1;    ch=getchar();}
    while(ch>='0'&&ch<='9')    {x=(x<<3)+(x<<1)+(ch^48);    ch=getchar();}
    return x*f;
}
const int p=100000;
int n,m,k,top,SUM;
ll ANS,ans[100050];
int sum[100050];
int v[100050],f[100050],s[100050],d[100050];
vector<int >S[100050];
vector<int >::iterator it;
pair<int ,int >t[100050];
priority_queue<pair<int ,int > >Q;
int main()
{
    n=read();    m=read();    k=read();
    for(int i=1;i<=n;++i)    v[i]=read(),f[i]=read(),s[i]=read(),d[i]=read();
    for(int i=1;i<=n;++i)
        if(!d[i])    S[p].push_back(i);
        else    S[min(p,(s[i]+d[i]-1)/d[i])].push_back(i);
    for(int i=p;i>=1;--i)
    {
        for(it=S[i].begin();it!=S[i].end();it++)
            Q.push(make_pair(v[*it]+f[*it],*it));
        int tmp=m; top=0;
        while(tmp&&!Q.empty())
        {
            int VAL=Q.top().first;    int POS=Q.top().second;    Q.pop();
            if(!sum[POS])
            {
                ANS+=VAL;    sum[POS]+=1;    tmp-=1;
                if(s[POS]!=sum[POS])    Q.push(make_pair(v[POS],POS));
            }
            else
            {
                int cnt=min(tmp,s[POS]-sum[POS]-(i-1)*d[POS]);
                ANS+=(ll)VAL*cnt;    sum[POS]+=cnt;    tmp-=cnt;
                if(s[POS]!=sum[POS])    t[++top]=make_pair(v[POS],POS);
            }
        }
        SUM+=m-tmp;
        while(top)    Q.push(t[top]),top--;
    }
    while(!Q.empty())    Q.pop();
    for(int i=1;i<=n;++i)
        if(sum[i]>1)    Q.push(make_pair(-v[i],i));
        else if(sum[i])    Q.push(make_pair(-v[i]-f[i],i));
    for(int i=p;i>=1;--i)
    {
        int tmp=max(0,SUM-i*m);
        while(tmp)
        {
            int VAL=Q.top().first;    int POS=Q.top().second;    Q.pop();
            if(sum[POS]>1)
            {
                int cnt=min(tmp,sum[POS]-1);
                ANS+=(ll)VAL*cnt;    sum[POS]-=cnt;    tmp-=cnt;
                if(sum[POS]>1)    Q.push(make_pair(-v[POS],POS));
                else if(sum[POS]==1)    Q.push(make_pair(-v[POS]-f[POS],POS));
            }
            else
                ANS+=VAL,sum[POS]-=1,tmp-=1;
        }
        SUM=min(SUM,i*m);    ans[i]=ANS;
    }
    while(k--)    printf("%lld
",ans[read()]);
    return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/wyher/p/11134980.html