本文共 6011 字，大约阅读时间需要 20 分钟。

传送门：

分析

这是一道有源汇上下界最大流的模板题（废话）。

既然是网络流的问题，故应该先将图建出来：

根据题目特征，

• 我们将少女和每一天看作是图中的点。

• 当然，因为每一天都有拍照次数的限制，我们可以加一个源点 \(s\) ，向每一天连边，这个边的容量范围是 \([0,D_i]\) 。

• 类似地，因为每个少女都有一个至少拍照张数的限定，所以加一个汇点 \(t\) ，然后让每个少女向汇点连边，容量范围自然是 \([G_i,∞]\) 。

• 至于少女和每一天，根据题意，她们之间连边的容量是 \([L, R]\) 。

至此，我们便将图建好了，从图的特征以及题意可以看出，这是一个求有源汇上下界最大流的问题。

怎么解决呢？

如果对约定的记号不熟悉可以看看我的博客：

无源汇上下界可行流

首先，先介绍一下无源汇上下界可行流的求法（即：可行循环流的求法）：

p.s. 如果会的可以直接跳过看下面的部分

对于可行循环流中的边 \((u,v)\) 有如下容量限制： \(\underline{c}(u,v)\le f(u,v) \le \overline{c}(u,v)\)

简单的想法是将问题转化为求有源汇最大流。转化的方法自然是构造，构造的原则是保证问题的等价。

构造方式：

加入虚拟源点 \(S\) ，虚拟汇点 \(T\) 。

对于每个点 \(x\)，记它的入边（假设入点为 \(u\) ）对应的容量下界为 \(\underline{c}(u,x)\) ，出边 （假设出点为 \(v\) ）对应的容量下界为 \(\underline{c}(x,v)\) 。

如果 \(c=\sum \underline{c}(u,x)-\sum \underline{c}(x,v)>0\) ，那么连边 \((S,x)\) ，容量为 \(c\) 。

如果 \(c=\sum \underline{c}(u,x)-\sum \underline{c}(x,v)<0\) ，那么连边 \((x,T)\) ，容量为 \(-c\) 。

根据上述规则得到新图 \(G'\) 。

只需证明：\(G'\) 的最大流与原图 \(G\) 的可行流是一一对应的。

证明一个流对应另一个流的方法：从一个流进行等价变换，所得到的新流仍然合法：即满足容量限制，流量守恒。

容量限制较容易证明，故本文出现的证明都是关于证明流量守恒的。

证明：

先证明 \(G\) 的一个可行流对应着 \(G'\) 的一个最大流（这里的最大流要求源点、汇点与其它点的连边满流，在接下来的讨论中可以发现需要这个约束）。

约定：点 \(x\) 的入点构成的集合为 \(U\) ，出点构成的集合为 \(V\) ，这样做可以省去求和 \(\sum\) ，表述方便，即 \(\sum \underline{c}(u,x)=c(U,x)\)
，\(\sum \underline{c}(x,v)=c(x,V)\) 等等。

对 \(G\) 的一个可行流，自然有： \(f(U,x)=f(x,V)\)

等价变形： \(f'(U,x)+\underline{c}(U,x)=f'(x,V)+\underline{c}(x,V)\)

进而有：\(f'(U,x)+\underline{c}(U,x)-\underline{c}(x,V)=f'(x,V)\)

不妨设 \(\underline{c}(U,x)-\underline{c}(x,V)>0\) ， 注意到 \(\underline{c}(U,x)-\underline{c}(x,V)\) 恰好是 \(c(S,x)\)，\(\underline{c}(U,x)-\underline{c}(x,V)<0\) 的情况同理，故对于新图，流量也是守恒的。

而且从中可以发现，这里的最大流要求源点、汇点与其它点的连边满流。

从上面的证明可以发现 \(G'\) 的一个最大流也对应着 \(G\) 的一个可行流，只需要将公式倒着写一遍即可（因为是恒等变换）。

至此，证明结束。

在具体操作的时候，要注意跑完最大流之后，对应的边需要加上补偿值才是所要求的网络（参见证明中的公式以及下面的代码）。

求取可行循环流具体过程可以见代码：

#include<bits/stdc++.h>using namespace std;const int N=205, M=12005+N<<1;const int INF=0x3f3f3f3f;int n, m, S, T;struct node{    int to, c, l, next;}e[M];int h[N], tot;void add(int u, int v, int lc, int uc){    e[tot].to=v, e[tot].c=uc-lc, e[tot].l=lc, e[tot].next=h[u], h[u]=tot++;    e[tot].to=u, e[tot].c=0, e[tot].next=h[v], h[v]=tot++;}int imo[N]; // in minus outint d[N], q[N], cur[N];bool bfs(){    memset(d, -1, sizeof d);    int tt=-1, hh=0;    q[++tt]=S, d[S]=0, cur[S]=h[S];    while(tt>=hh){        int hd=q[hh++];        for(int i=h[hd]; ~i; i=e[i].next){            int go=e[i].to;            if(d[go]==-1 && e[i].c){                cur[go]=h[go];                d[go]=d[hd]+1;                if(go==T) return true;                q[++tt]=go;            }        }    }    return false;}int find(int u, int limit){    if(u==T) return limit;    int flow=0;    for(int i=cur[u]; ~i && limit>flow; i=e[i].next){        int go=e[i].to;        cur[u]=i;        if(e[i].c && d[go]==d[u]+1){            int t=find(go, min(limit-flow, e[i].c));            if(!t) d[go]=-1;            flow+=t, e[i].c-=t, e[i^1].c+=t;        }    }    return flow;}int dinic(){    int res=0, flow;    while(bfs()) while(flow=find(S, INF)) res+=flow;    return res; }int main(){    memset(h, -1, sizeof h);    cin>>n>>m;    S=0, T=n+1;    for(int i=1; i<=m; i++){        int u, v, lc, uc; cin>>u>>v>>lc>>uc;        add(u, v, lc, uc);        imo[u]-=lc, imo[v]+=lc;    }       int tot=0;    for(int i=1; i<=n; i++)        if(imo[i]>0) add(S, i, 0, imo[i]), tot+=imo[i];        else if(imo[i]<0) add(i, T, 0, -imo[i]);    if(dinic()!=tot) puts("NO");    else{        puts("YES");        for(int i=0; i<2*m; i+=2) cout<<e[i].l+e[i^1].c<<endl;    }    return 0;}

接下来求有源汇上下界最大流：

在上面，我们已经知道了怎样求无源汇上下界可行流，那先看看有源汇上下界可行流怎么求：方法其实很简单，将汇点 \(t\) 向源点 \(s\) 连一条容量 \(∞\) 的边（我们称之为虚边）即可，有个直观的比喻：就像是在汇点 \(t\) 连接一台水泵，将源点 \(s\) 流往 汇点 \(t\) 的水重新泵上去。这样做就将问题转换为了熟悉的无源汇上下界可行流问题。

简单来说：

\(t\) 向源点 \(s\) 连一条容量 \(∞\) 的边，得到循环流。

从虚拟源点 \(S\) 向 \(T\) 跑一遍最大流。

记录 \(t\) 向 \(s\) 连的边的流量（即虚边流量 \(res_1\) ），然后断开虚边，从 \(s\) 向 \(t\) 跑一遍最大流得到新增的流量 \(res_2\) ，答案就是 \(res_1+res_2\) 。

注意到，无源汇上下界可行流对应的流网络与虚拟源汇点 \(S,T\) 相连的边都是满流，所以在跑完一遍最大流之后，与虚拟源汇点 \(S,T\) 相连的边都不可能再被用到，我们可以直接将它们全部拆掉，然后，再将虚边（水泵）拆掉，发现只需要加回补偿值（但事实上，因为 \(t\) 向 \(s\) 连的边容量范围是 \([0,∞)\) ，不需要进行补偿），所得到的流就是一个合法的有源汇上下界可行流了。

也就是说新图的可行流和原图（没有经过变换的，最原始的）的可行流是一一对应的，那么新图的最大流也必然是对应着原图的最大流了。

因此，最后我们从 \(s\) 向 \(t\) 跑一遍最大流即可。

代码：

#include<bits/stdc++.h>using namespace std;const int N=1550, M=365+1000+365*1000+N<<1, INF=0x3f3f3f3f; int n, m, s, t, S, T;struct node{	int to, c, next;}e[M];int h[N], tot;// 连边函数，有这样的性质：正向边^1=反向边void add(int u, int v, int c){	e[tot].to=v, e[tot].c=c, e[tot].next=h[u], h[u]=tot++;	e[tot].to=u, e[tot].c=0, e[tot].next=h[v], h[v]=tot++;}int imo[N]; // imo 的意思是： in minus out 入减去出int q[N], d[N], cur[N];bool bfs(){	memset(d, -1, sizeof d);	int tt=-1, hh=0;	q[++tt]=S, d[S]=0, cur[S]=h[S];	while(tt>=hh){		int hd=q[hh++];		for(int i=h[hd]; ~i; i=e[i].next){			int go=e[i].to;			if(d[go]==-1 && e[i].c){				d[go]=d[hd]+1;				cur[go]=h[go];				if(go==T) return true;				q[++tt]=go;			}		}	}	return false;}int find(int u, int limit){	if(u==T) return limit;	int flow=0;	for(int i=cur[u]; ~i && limit>flow; i=e[i].next){		int go=e[i].to;		cur[u]=i; // 当前弧优化		if(d[go]==d[u]+1 && e[i].c){			int t=find(go, min(e[i].c, limit-flow));			if(!t) d[go]=-1;			e[i].c-=t, e[i^1].c+=t, flow+=t;		}	}	return flow;}int dinic(){	int res=0, flow;	while(bfs()) while(flow=find(S, INF)) res+=flow;	return res;}int main(){	while(cin>>n>>m){		memset(h, -1, sizeof h), tot=0;		memset(imo, 0, sizeof imo);				s=0, t=n+m+1, S=n+m+2, T=S+1;		for(int i=1; i<=m; i++){			int G; cin>>G;			add(i, t, INF-G);			imo[i]-=G, imo[t]+=G;		}				for(int i=m+1; i<=m+n; i++){			int C, D; cin>>C>>D;			add(s, i, D); // 范围是 [0,D] 因此不需要更新 imo[]			while(C--){				int id, lc, uc; cin>>id>>lc>>uc;				id++;				add(i, id, uc-lc);				imo[i]-=lc, imo[id]+=lc;			}		}				int cnt=0;		for(int i=0; i<=n+m+1; i++)			if(imo[i]>0) add(S, i, imo[i]), cnt+=imo[i];			else if(imo[i]<0) add(i, T, -imo[i]);				add(t, s, INF); // 添加“水泵”				if(dinic()!=cnt) cout<<-1<<endl<<endl;		else{			int res=e[tot-1].c;			e[tot-1].c=0, e[tot-2].c=0;			S=s, T=t;			res+=dinic();			cout<<res<<endl<<endl;		}	}	return 0;}