写在退役之前：P5192 【模板】有源汇上下界最大流-526互联

2018年，欲学 OI，被某机构骗去学 Python，结果啥都没学到。

2019年末，终于开始学 C++

2021年4月，摆脱了某机构。

2021年9月，未过初赛

2022年6月，中考失败

2022年7月，自招失败

2022年10月，CSP 失败

2022年11月，NOIP 失败

2023年2月25日，我准备开始写下这篇文章，因为我不知道我还能打多久的OI。

也许是一位女同学的长久鼓励（我喜欢她很久了，她也知道），我没有彻底放弃自己，不知道这算不算是各位口中的 npy，但是她对我的帮助是精神上的。她今天（2023年2月25日）和我聊了聊，让我有了重新拿起电脑的勇气，在这之前，我已经两个月没有摸电脑了。

在我是一位选手一点时间里，写下了

半退役好久了，现在在竞赛上的压力小了很多，就随便学点东西吧。

之前老早就学了网络流，发现有个叫上下界网络流的东西，于是打算学一下。

例题：Loj#116

这道题是纯模板，代码比较简单：

signed main(){
    scanf("%d%d%d%d",&n,&m,&a,&b);
    s=N-1,t=N-2;
    for(int i=1;i<=m;i++){
        int u,v,l,r;
        scanf("%d%d%d%d",&u,&v,&l,&r);
        in[v]+=l,in[u]-=l;
        add(u,v,r-l);
    }
    for(int i=1;i<=n;i++){
        if(in[i]>0)all+=in[i],add(s,i,in[i]);
        else add(i,t,-in[i]);
    }
    add(b,a,inf);
    if(all!=dinic())puts("please go home to sleep");
    else{
        s=a,t=b;
        all=val[tot];
        val[tot-1]=val[tot]=0;
        printf("%d\n",dinic()+all);
    }
    return 0;
}

新建一对源点汇点
先建一个正常的网络流，每条边为上下界的差。
记录下每个点的初始入流和出流
然后如果那个点是入流更多，那么就从源点补上，否则就将多余流出的流向汇点。
理解一下这个过程，如果某个节点入度多了，就从前面凑，如果出度多了，就往后边使命流。每条边的最大承受量就是上限减下限。

现在我们就完成了无源汇上下界网络流的操作了。

例题：Loj#115

有源汇也很简单，只需要再在给定源点汇点的残留网络上跑一遍最大流即可，最后的答案就是最大流+残留网络最大流。

s=a,t=b;
all=val[tot];
val[tot-1]=val[tot]=0;
printf("%d\n",dinic()+all);

于是我们有了理论基础，现在看到我们的洛谷《模板题》：

P5192

简单分析一下就可以发现，这道题实际上很简单，就是一个模板，但是输入量有点庞大，细节有亿点多。

对于每一天建立一个节点，每个少女也建立一个节点。

源点向每一天连一条容量为当天限制 $D_iDi 的边。$

每一天与那一天拍照的少女连一条边，上界

最后每个少女往汇点连一条，上界 $+\infty+∞，下界 GG。$

然后跑一边有源汇上下界网络流即可。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define N 2145141
#define inf 2147483647
using namespace std;
int n,m;
int au[N],av[N],al[N],ar[N],cnt,all;
int head[N],to[N],nxt[N],val[N],tot,in[N],a,b,s,t;
int d[N]; 
void add(int u,int v,int w){
    to[++tot]=v;
    nxt[tot]=head[u];
    head[u]=tot;
    val[tot]=w;
    to[++tot]=u;
    nxt[tot]=head[v];
    head[v]=tot;
    val[tot]=0;
}
void addc(int u,int v,int l,int r){
    add(u,v,r-l);
    in[u]-=l;in[v]+=l;
}
bool bfs(){
    queue<int>q;
    q.push(s);
    memset(d,-1,sizeof(d));
    d[s]=0;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=nxt[i]){
            if(!val[i])continue;
            int y=to[i];
            if(d[y]==-1){
                d[y]=d[x]+1;
                if(y==t)return 1;
                q.push(y);
            }
        }
    }
    return 0;
}
int dfs(int x,int a){
    if(!a||x==t)return a;
    int res=a;
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(val[i]&&d[x]+1==d[y]){
            int tmp=dfs(y,min(val[i],res));
            res-=tmp;
            val[i]-=tmp;
            val[i^1]+=tmp;
            if(res==0)return a;
        }
    }
    if(a==res)d[x]=-1;
    return a-res;
}
int dinic(){
    int flow=0;
    while(bfs())flow+=dfs(s,inf);   
    return flow;
} 
signed main(){
    //freopen("P5192_1.in","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF){
        tot=1,cnt=0;
        s=N-3,t=N-4;
        a=n+m+1,b=n+m+2;
        memset(head,0,sizeof(head));
        memset(in,0,sizeof(in));
        all=0;
        for(int i=1;i<=m;i++){
            int g;
            scanf("%d",&g);
            addc(i+n,b,g,inf);
        }
        for(int i=1;i<=n;i++){
            int c,d;
            scanf("%d%d",&c,&d);
            add(a,i,d);
            for(int j=1;j<=c;j++){
                int t,l,r;
                scanf("%d%d%d",&t,&l,&r);
                addc(i,n+t+1,l,r);
            }
        }
        for(int i=1;i<=m+n+2;i++){
            if(in[i]>0){
                add(s,i,in[i]);
                all+=in[i];
            }
            if(in[i]<0)add(i,t,-in[i]); 
        }
        add(b,a,inf);
        if(all>dinic())puts("-1\n");
        else{
            all=val[tot];
            val[tot]=val[tot-1]=0;
            s=a,t=b;
            printf("%d\n\n",dinic()+all);
        }
    }
    return 0;
}