【网络流】有源汇上下界最大流
传送门：//www.luogu.com.cn/problem/P5192
分析
这是一道有源汇上下界最大流的模板题（废话）。
既然是网络流的问题，故应该先将图建出来：
根据题目特征，
-
我们将少女和每一天看作是图中的点。
-
当然，因为每一天都有拍照次数的限制，我们可以加一个源点 \(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 out
int 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;
}
