有源汇的上下界最大/小流

（一）#116. 有源汇有上下界最大流

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
const int inf=0x3f3f3f3f;
const int p=998244353;
const int mod=998244353;
const int g=3;
const int maxn=410;
const int maxm=40010;
int head[maxn],ver[maxm],edge[maxm],nt[maxm];
int d[maxn],in[maxn],out[maxn];
int n,m,s,t,tot=1,nows,nowt,ss,tt;
queue<int>q;


void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z,nt[tot]=head[x],head[x]=tot;
    ver[++tot]=x,edge[tot]=0,nt[tot]=head[y],head[y]=tot;
}

bool bfs(void)
{
    memset(d,0,sizeof(d));
    while(q.size()) q.pop();

    q.push(s);
    d[s]=1;

    while(q.size())
    {
        int x=q.front();
        q.pop();

        for(int i=head[x];i;i=nt[i])
        {
            int y=ver[i];
            if(edge[i]&&!d[y])
            {
                q.push(y);
                d[y]=d[x]+1;
                if(y==t) return true;
            }
        }
    }
    return false;
}

int dinic(int x,int flow)
{
    if(x==t) return flow;
    int rest=flow ,k;

    for(int i=head[x];i&&rest;i=nt[i])
    {
        int y=ver[i];
        if(edge[i]&&d[y]==d[x]+1)
        {
            k=dinic(y,min(rest,edge[i]));
            if(!k) d[y]=0;
            edge[i]-=k;
            edge[i^1]+=k;
            rest-=k;
        }
    }
    return flow-rest;
}

int getmaxx(void)
{
    int maxflow=0;
    int flow=0;
    while(bfs())
        while(flow=dinic(s,inf))
            maxflow+=flow;
    return maxflow;
}

void fail(void)
{
    puts("please go home to sleep");
}

int main(void)
{
    scanf("%d%d%d%d",&n,&m,&nows,&nowt);
    int x,y,lo,up;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&x,&y,&lo,&up);
        out[x]+=lo,in[y]+=lo;
        add(x,y,up-lo);
    }
    ss=n+1,tt=n+2;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        if(in[i]>out[i]) add(ss,i,in[i]-out[i]);
        else add(i,tt,out[i]-in[i]);
        sum+=max(in[i]-out[i],0);
    }

    add(nowt,nows,inf);

    int ans=0;
    s=ss,t=tt;

    if(getmaxx()!=sum)
    {
        fail();
        return 0;
    }

    ans+=edge[tot];
    edge[tot]=edge[tot^1]=0;

    s=nows,t=nowt;
    ans+=getmaxx();
    printf("%d\n",ans);

    return 0;
}

（二）#117. 有源汇有上下界最小流

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
const int inf=0x3f3f3f3f;
const int p=998244353;
const int mod=998244353;
const int g=3;
const int maxn=50010;
const int maxm=400100;
int head[maxn],ver[maxm],edge[maxm],nt[maxm];
int d[maxn],in[maxn],out[maxn];
int n,m,s,t,tot=1,nows,nowt,ss,tt;
queue<int>q;


void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z,nt[tot]=head[x],head[x]=tot;
    ver[++tot]=x,edge[tot]=0,nt[tot]=head[y],head[y]=tot;
}

bool bfs(void)
{
    memset(d,0,sizeof(d));
    while(q.size()) q.pop();

    q.push(s);
    d[s]=1;

    while(q.size())
    {
        int x=q.front();
        q.pop();

        for(int i=head[x];i;i=nt[i])
        {
            int y=ver[i];
            if(edge[i]&&!d[y])
            {
                q.push(y);
                d[y]=d[x]+1;
                if(y==t) return true;
            }
        }
    }
    return false;
}

int dinic(int x,int flow)
{
    if(x==t) return flow;
    int rest=flow ,k;

    for(int i=head[x];i&&rest;i=nt[i])
    {
        int y=ver[i];
        if(edge[i]&&d[y]==d[x]+1)
        {
            k=dinic(y,min(rest,edge[i]));
            if(!k) d[y]=0;
            edge[i]-=k;
            edge[i^1]+=k;
            rest-=k;
        }
    }
    return flow-rest;
}

int getmaxx(void)
{
    int maxflow=0;
    int flow=0;
    while(bfs())
        while(flow=dinic(s,inf))
            maxflow+=flow;
    return maxflow;
}

void fail(void)
{
    puts("please go home to sleep");
}

int main(void)
{
    scanf("%d%d%d%d",&n,&m,&nows,&nowt);
    int x,y,lo,up;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&x,&y,&lo,&up);
        out[x]+=lo,in[y]+=lo;
        add(x,y,up-lo);
    }
    ss=n+1,tt=n+2;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        if(in[i]>out[i]) add(ss,i,in[i]-out[i]);
        else add(i,tt,out[i]-in[i]);
        sum+=max(in[i]-out[i],0);
    }

    add(nowt,nows,inf);

    int ans=0;
    s=ss,t=tt;

    if(getmaxx()!=sum)
    {
        fail();
        return 0;
    }

    ans+=edge[tot];
    edge[tot]=edge[tot^1]=0;

    s=nowt,t=nows;
    ans-=getmaxx();
    printf("%d\n",ans);

    return 0;
}

（三）P5192 Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流

注意：少女编号从0开始。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
const int inf=0x3f3f3f3f;
const int p=998244353;
const int mod=998244353;
//const int g=3;
const int maxn=410;
const int maxm=1100;
int head[maxn+maxm],ver[maxn*maxm],edge[maxn*maxm],nt[maxn*maxm];
int d[maxn+maxm],in[maxn+maxm],out[maxn+maxm];
int n,m,s,t,tot=1,nows,nowt,ss,tt;
queue<int>q;
int nd[maxn],ng[maxm],cnt=0;

void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z,nt[tot]=head[x],head[x]=tot;
    ver[++tot]=x,edge[tot]=0,nt[tot]=head[y],head[y]=tot;
}

bool bfs(void)
{
    memset(d,0,sizeof(d));
    while(q.size()) q.pop();

    q.push(s);
    d[s]=1;

    while(q.size())
    {
        int x=q.front();
        q.pop();

        for(int i=head[x];i;i=nt[i])
        {
            int y=ver[i];
            if(edge[i]&&!d[y])
            {
                q.push(y);
                d[y]=d[x]+1;
                if(y==t) return true;
            }
        }
    }
    return false;
}

int dinic(int x,int flow)
{
    if(x==t) return flow;
    int rest=flow ,k;

    for(int i=head[x];i&&rest;i=nt[i])
    {
        int y=ver[i];
        if(edge[i]&&d[y]==d[x]+1)
        {
            k=dinic(y,min(rest,edge[i]));
            if(!k) d[y]=0;
            edge[i]-=k;
            edge[i^1]+=k;
            rest-=k;
        }
    }
    return flow-rest;
}

int getmaxx(void)
{
    int maxflow=0;
    int flow=0;
    while(bfs())
        while(flow=dinic(s,inf))
            maxflow+=flow;
    return maxflow;
}

void fail(void)
{
    puts("-1\n");
}

int main(void)
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(head,0,sizeof(head));
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        tot=1,cnt=0;
        for(int i=1;i<=n;i++) nd[i]=++cnt;
        for(int i=0;i<m;i++) ng[i]=++cnt;
        nows=++cnt,nowt=++cnt,ss=cnt+1,tt=ss+1;

        int gg;
        for(int i=0;i<m;i++)
        {
            scanf("%d",&gg);
            out[ng[i]]+=gg,in[nowt]+=gg;
            add(ng[i],nowt,inf-gg);
        }

        int cc,dd;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&cc,&dd);
            out[nows]+=0,in[nd[i]]+=0;
            add(nows,nd[i],dd);

            int t,l,r;
            for(int j=1;j<=cc;j++)
            {
                scanf("%d%d%d",&t,&l,&r);
                out[nd[i]]+=l,in[ng[t]]+=l;
                add(nd[i],ng[t],r-l);
            }
        }

        int sum=0;
        for(int i=1;i<=cnt;i++)
        {
            if(in[i]>out[i]) add(ss,i,in[i]-out[i]);
            else add(i,tt,out[i]-in[i]);
            sum+=max(in[i]-out[i],0);
        }
        add(nowt,nows,inf);

        s=ss,t=tt;
        if(getmaxx()!=sum)
        {
            fail();
            continue;
        }

        int ans=edge[tot];
        edge[tot]=edge[tot^1]=0;
        s=nows,t=nowt;
        ans+=getmaxx();
        printf("%d\n\n",ans);
    }

    return 0;
}