有/无源汇的上下界可行流

· · 个人记录

无源汇的上下界可行流

对于普通的网络流问题，设 f_{u,v} 为边 (u,v) 的流量， cap_{u,v} 为边 (u,v) 之间的容量，其有限制为

\displaystyle \sum{f_{u,i}} = \displaystyle \sum{f_{i,v}} \\ 0 \leq f_{u,i} \leq cap_{u,i}

而对于上下界可行流，设 f_{u,v} 为边 (u,v) 的流量， max_{u,v} 为边 (u,v) 之间的容量上限， min_{u,v} 为边 (u,v) 之间的容量下限，有限制为

\displaystyle \sum{f_{u,i}} = \displaystyle \sum{f_{i,v}} \\ min_{u,v} \leq f_{u,v} \leq max_{u,v} \\

实际上只是增加了流量的下限要求，即为流量平衡条件和流量限制条件

那么对于给定的一张图，设 max_{u,v} 为容量上限， min_{u,v} 为容量下限，有如下建图方式：

  1. 设立一个超级源点和超级汇点，记为 s 和 t
  2. 对于原先图中的一条边 (u,v) ，在 u 和 v 之间连一条容量为 max_{u,v} - min_{u,v} 的边
  3. 记录一个 d 数组，用以记录节点 i 的所有入边的容量下限之和与所有出边的容量下限之和的差
  4. 对于一个节点 i ，如果其 d[i] 小于 0 ，那么就从该节点向 t 连一条容量为 -d[i] 的边
  5. 对于一个节点 i ，如果其 d[i] 大于 0 ，那么就从 s 向该节点连一条容量为 d[i] 的边
  6. 以 s 为起点， t 为终点跑一遍最大流，再加上所有边的容量下限即得答案

考虑这种建边方式的正确性

因为我们有一个容量上限和一个容量下限，而容量下限的条件并不容易满足，所以考虑对该点容量的上限和下限同时减去下限的容量，那么这里就可以将容量下限的限制条件消除，那么新的图上的边的当前流量为 g_{i,j} 时，其最终的实际流量为 f_{i,j} = g_{i,j} + min_{i,j}

但是显然这样是不对的，所以我们考虑对这个节点进行补流，而根据流量平衡条件，实际上一个节点在最大流中最后的流量分配可以不用关系，只需要保证其流量的平衡

那么为了

\displaystyle \sum{f_{u,i}} = \displaystyle \sum{f_{i,v}}

即

\displaystyle \sum{g_{u,i} + min_{u,i}} = \displaystyle \sum_{g_{i,v} + min_{i,v}}

整理可得：

\displaystyle \sum{min_{u,i}} - \displaystyle \sum{min_{i,v}} = \displaystyle \sum{g_{u,i}} - \displaystyle \sum{g_{i,v}}

所以在上面就需要维护一个 d 数组，那么就是 d[i] = \displaystyle \sum{min_{u,i}} - \displaystyle \sum{min_{i,v}} ，那么如果 d[i] 小于 0 ，也就是说此时其入边的流量之和大于出边的流量之和，但是为了保证当前图上的流量平衡，我们就需要帮他引流，就需要增大它流出的流量，使其流量平衡，所以从当前节点向 t 连一条容量为 -d[i] 的边进行扩流，同理，当 d[i] 大于 0 的时候，我们就从 s 向当前节点连一条容量为 d[i] 的边进行扩流

最后得到的原图和当前图的流量都是平衡的，且满足其流量限制条件

有源汇的上下界最大流

有源汇的上下界网络流模板

仍然建立超级源点 ss 和超级源点 tt ，其原先的源点和汇点记为 s 和 t ，其建边方式与无源汇的上下界最大流一样，最后再增加一条从 t 到 s 的容量下界为 0 ，上界为 \infty 的边即可

那么先以 ss 和 tt 跑一遍最大流，记答案为 ans_1 ，此时如果当前的超级源汇点是满流的，就说明存在可行流，那么再将 s 和 t 之间的边都拆掉，在新的图上以 s 为起点，以 t 为终点再跑一遍最大流，记为 ans_2 ，那么 ans_1+ans_2 即为答案

因为在存在 ss 和 tt 的时候，如果存在可行流（即超级源点和超级汇点的边满流），那么附加出来用来扩流和分流的边都已经使用了，就是跑出了 min_{i,j} 的最大流，那么拆掉 (t,s) 之间的边，原先的图就变为一个普通的网络流图，再跑一遍即可处理得到限制后的最大流（即 g_{i,j}），所以两者相加就是答案

那么考虑这道题

类似二分图，可以将天数置为左侧的点，而少女置为右侧的点，将源点向天数连边，将少女向汇点连边，之后天数与少女之间再连边，一个少女至少有 G_x 张照片刊登，那么代表这条边的容量下限为 G_x ，而上限为 \infty ，每一天文文最多拍 D_i 张照片，那么就是代表第 i 天与源点之间的边的容量上限为 D_i ，每一天的少女都要拍照数量在 [L,R] 之间，那么就是说明天数与少女之间的边的容量下限为 L ，容量上限为 R

跑有源汇的上下界最大流即可

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<math.h>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define ld long double

inline ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}

const ll inf=1e9+10;
const ll maxn=1e6+10;
const ll maxm=2e6+10;
ll n,m,s,t,s1,t1,s2,t2,sum,maxflow,tot=1;
ll head[maxm<<1],d[maxn],now[maxn],g[maxn],D[maxn];
struct node
{
    ll v,nxt,cap;
} e[maxm<<1];

inline void add(ll u,ll v,ll cap)
{
    e[++tot].v=v;
    e[tot].cap=cap;
    e[tot].nxt=head[u];
    head[u]=tot;
}

inline bool bfs()
{
    std::queue<ll> q;
    memset(d,0,sizeof(d));
    q.push(s);
    d[s]=1;
    now[s]=head[s];
    while(q.size())
    {
        ll u=q.front();
        q.pop();

        for(int i=head[u];i;i=e[i].nxt)
        {
            ll v=e[i].v;
            ll w=e[i].cap;

            if(!d[v]&&w)
            {
                d[v]=d[u]+1;
                now[v]=head[v];
                q.push(v);

                if(v==t) return true;
            }
        }
    }
    return false;
}

inline ll dinic(ll x,ll flow)
{
    if(x==t||!flow) return flow;
    ll ret=flow;

    for(int i=now[x];i&&ret;i=e[i].nxt)
    {
        ll v=e[i].v;
        ll w=e[i].cap;
        now[x]=i;

        if(d[v]==d[x]+1&&w)
        {
            ll k=dinic(v,std::min(ret,w));

            if(!k) d[v]=0;

            e[i].cap-=k;
            e[i^1].cap+=k;
            ret-=k;
        }
    }

    return flow-ret;
}

int main(void)
{
    while(scanf("%lld %lld",&n,&m)!=EOF)
    {
        memset(head,0,sizeof(head));
        memset(d,0,sizeof(d));
        memset(now,0,sizeof(now));
        tot=1;
        sum=0,maxflow=0;

        s1=0,t1=n+m+1;
        s2=t1+1,t2=t1+2;

        for(int i=1;i<=m;i++)
        {
            scanf("%lld",&g[i]);
            add(i+n,t1,inf-g[i]);
            add(t1,i+n,0);
            d[t1]+=g[i];
            d[i+n]-=g[i];
        }

        for(int i=1;i<=n;i++)
        {
            ll c,v,l,r;
            scanf("%lld",&c);
            scanf("%lld",&D[i]);
            add(s1,i,D[i]);
            add(i,s1,0);
            for(int j=1;j<=c;j++)
            {
                scanf("%lld %lld %lld",&v,&l,&r);
                v++;
                add(i,v+n,r-l);
                add(v+n,i,0);
                d[v+n]+=l;
                d[i]-=l;
            }
        }

        for(int i=0;i<=n+m+1;i++)
        {
    //      printf("%lld\n",d[i]);
            if(d[i]<0) add(i,t2,-d[i]),add(t2,i,0); 
            if(d[i]>0) add(s2,i,d[i]),add(i,s2,0),sum+=d[i];
        }

        add(t1,s1,inf);
        add(s1,t1,0);

        s=s2,t=t2;

        while(bfs())
        {
            ll flow;
            while(flow=dinic(s,inf)) maxflow+=flow;
        }

        if(maxflow<sum)
        {
            printf("-1\n\n");
            continue;
        }

        s=s1,t=t1;

        maxflow=0;

        maxflow+=e[tot].cap;
        e[tot].cap=0;
        e[tot-1].cap=0;

        while(bfs())
        {
            ll flow;
            while(flow=dinic(s,inf)) maxflow+=flow;
        }

        printf("%lld\n\n",maxflow);
    }
    return 0;
}

有源汇的上下界最小流

建图方式与无源汇的上下界可行流相同

先求 ss 到 tt 的最大流，再将 (t,s) 的边加上，重新跑最大流，答案即为 (t,s) 边的实际流量

因为最初没有 (t,s) 的边的时候，会尽可能地将流向其他的边去流，而加上这条边之后，流过这条边的流量就是剩余的流量，那么就是最小流

最小费用可行流

建边方式与有源汇的上下界可行流相同，只是加入了花费，建图的时候对原图中对应的边连花费为 cost 的边，其余边的费用设置为 0 ，那么就是从 ss 到 tt 跑最小费用最大流，之后再加上原图中边的容量下界与费用的乘积即可

注意这里有上下界的费用流中是指满足流量限制条件和流量平衡条件下的最小费用，而并不用满足其最大流的限制

那么本题中，源点实际上就是 1 ，而汇点单独设置，从所有的点向汇点连容量为 \infty ，花费为 0 的边，代表可以随意地从当前节点位置停止，重新开始，而不限制次数

同时，对于原图中就有的边，在网络流图中的边的要求就是容量下限为 1 ，上限为 \infty

按照最小费用可行流的建图方式去建图，然后跑最小费用最大流，最后将所有边的花费加上即可（因为有花费限制的边的容量下限为 1 ）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<math.h>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define ld long double

inline ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}

const ll inf=1e9+10;
const ll maxn=15000+10;
const ll maxm=2e6;
ll n,s,t,ss,tt,tot=1,maxflow,mincost;
ll head[maxm<<1],d[maxn],flow[maxn],cost[maxn],pre[maxn],idx[maxn],vis[maxn];
struct node
{
    ll v,nxt,cap,cost;
} e[maxm<<1];

inline void add(ll u,ll v,ll cap,ll cost)
{
    e[++tot].v=v;
    e[tot].cap=cap;
    e[tot].cost=cost;
    e[tot].nxt=head[u];
    head[u]=tot;
}

inline bool spfa()
{
    std::queue<ll> q;
    memset(flow,0x3f,sizeof(flow));
    memset(cost,0x3f,sizeof(cost));
    memset(vis,0,sizeof(vis));
    q.push(ss);
    vis[ss]=1;
    cost[ss]=0;
    pre[tt]=-1;
    while(q.size())
    {
        ll u=q.front();
        q.pop();

        vis[u]=0;

        for(int i=head[u];i;i=e[i].nxt)
        {
            ll v=e[i].v;
            ll co=e[i].cost;
            ll cap=e[i].cap;

            if(cost[v]>cost[u]+co&&cap)
            {
                cost[v]=cost[u]+co;
                flow[v]=std::min(flow[u],cap);
                pre[v]=u;
                idx[v]=i;

                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return pre[tt]!=-1;
}

inline void Min_Cost_Max_Flow()
{
    while(spfa())
    {
        maxflow+=flow[tt];
        mincost+=flow[tt]*cost[tt];
        ll now=tt;
        while(now!=ss)
        {
            e[idx[now]].cap-=flow[tt];
            e[idx[now]^1].cap+=flow[tt];
            now=pre[now];
        }
    }
}

int main(void)
{
    n=read();
    s=1,t=n+1;
    ss=0,tt=n+2;

    for(int i=1;i<=n;i++)
    {
        ll k=read();
        for(int j=1;j<=k;j++)
        {
            ll v=read(),w=read();
            d[v]++;
            d[i]--;
            mincost+=w;
            add(i,v,inf,w);
            add(v,i,0,-w);
        }
    }

    for(int i=2;i<=n;i++)
    {
        add(i,t,inf,0);
        add(t,i,0,0);
    }

    for(int i=1;i<=t;i++)
    {
        if(d[i]<0) add(i,tt,-d[i],0),add(tt,i,0,0);
        if(d[i]>0) add(ss,i,d[i],0),add(i,ss,0,0);
    }

    add(t,s,inf,0),add(s,t,0,0);

    Min_Cost_Max_Flow();

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

    return 0;
}