有上下界的网络流
在沈阳的网络赛遇到一道求上下界网络流的模板题，虽然可以用贪心做，但毕竟是模板题，学习一下。原作者：https://www.cnblogs.com/liu-runda/p/6262832.html
- 引
有上下界的网络流的核心是调整,我们通过一个初始的未必可行的流调整出一个可行流,还可以从可行的未必最大/最小的流调整出最大/最小流.
另一个常用技巧是有源汇的流和无源汇的流(循环流)的转换.除了无源汇可行流的求解,其他有源汇的上下界网络流都要用到这个技巧.
可行流：容量网络G中满足以下条件的网络流f,称为可行流:
弧流量限制条件: 0<=f(u,v)<=c(u,v);
守恒条件:即流入一个点的流量要等于流出这个点的流量,(源点和汇点除外).
无源汇有上下界可行流（循环流）
模型:一个网络,求出一个流,使得每条边的流量必须>=Li且<=Hi,每个点必须满足总流入量=总流出量(流量守恒)(这个流的特点是循环往复,无始无终).
这个算法是有上下界网络流算法的基础,只要深刻理解这个算法其他算法也就水到渠成。
可行流算法的核心是将一个不满足流量守恒的初始流调整成满足流量守恒的流.
流量守恒,即每个点的总流入量=总流出量
如果存在一个可行流,那么一定满足每条边的流量都大于等于流量的下限.因此我们可以令每条边的流量等于流量下限,得到一个初始流,然后建出这个流的残量网络.(即:每条边的流量等于这条边的流量上限与流量下限之差)
这个初始流不一定满足流量守恒,因此最终的可行流一定是在这个初始流的基础上增大了一些边的流量使得所有点满足流量守恒.
因此我们考虑在残量网络上求出一个另不满足流量守恒的附加流,使得这个附加流和我们的初始流合并之后满足流量守恒.即:
- 如果某个点在所有边流量等于下界的初始流中满足流量守恒,那么这个点在附加流中也满足流量守恒,
- 如果某个点在初始流中的流入量比流出量多x,那么这个点在附加流中的流出量比流入量多x.
- 如果某个点在初始流中的流入量比流出量少x,那么这个点在附加流中的流出量比流入量少x.
可以认为附加流中一条从u到v的边上的一个流量代表将原图中u到v的流量增大1
X的数值可以枚举x的所有连边求出.比较方便的写法是开一个数组A[],A[i]表示i在初始流中的流入量-流出量的值,那么A[i]的正负表示流入量和流出量的大小关系,下面就用A[i]表示初始流中i的流入量-流出量
但是dinic算法能够求的是满足流量守恒的有源汇最大流,不能在原网络上直接求一个这样的无源汇且不满足流量守恒的附加流.注意到附加流是在原网络上不满足流量守恒的,这启发我们添加一些原网络之外的边和点,用这些边和点实现”原网络上流量不守恒”的限制.
具体地,如果一个点i在原网络上的附加流中需要满足流入量>流出量(初始流中流入量<流出量,A[i]<0),那么我们需要给多的流入量找一个去处,因此我们建一条从i出发流量=-A[i]的边.如果A[i]>0,也就是我们需要让附加流中的流出量>流入量,我们需要让多的流出量有一个来路,因此我们建一条指向i的流量=A[i]的边.
当然,我们所新建的从i出发的边也要有个去处,指向i的边也要有个来路,因此我们新建一个虚拟源点ss和一个虚拟汇点tt(双写字母是为了和有源汇网络流中的源点s汇点t相区分).新建的指向i的边都从ss出发,从i出发的边都指向tt.一个点要么有一条边指向tt,要么有一条边来自ss,
指向tt的边的总流量上限一定等于ss流出的边的总流量上限,因为每一条边对两个点的du[i]贡献一正一负大小相等,所以全部点的du[i]之和等于0,即小于0的du[i]之和的绝对值=大于0的du[i]之和的绝对值.
如果我们能找到一个流满足新加的边都满流,这个流在原图上的部分就是我们需要的附加流(根据我们的建图方式,“新加的边都满流”和”附加流合并上初始流得到流量平衡的流”是等价的约束条件).
那么怎样找出一个新加的边都满流的流呢?可以发现假如存在这样的方案,这样的流一定是我们所建出的图的ss-tt最大流,所以跑ss到tt的最大流即可.如果最大流的大小等于ss出发的所有边的流量上限之和(此时指向tt的边也一定满流,因为这两部分边的流量上限之和相等).
最后,每条边在可行流中的流量=容量下界+附加流中它的流量(即跑完dinic之后所加反向边的权值).
建图模型：
以前写的最大流默认的下界为0，而这里的下界却不为0，所以我们要进行再构造让每条边的下界为0，这样做是为了方便处理。对于每根管子有一个上界容量up和一个下界容量low，我们让这根管子的容量下界变为0，上界为up-low。可是这样做了的话流量就不守恒了，为了再次满足流量守恒，我们增设一个超级源点st和一个超级终点sd。我们开设一个数组du[]来记录每个节点的流量情况。
du[i]=in[i]（i节点所有入流下界之和）-out[i]（i节点所有出流下界之和）。
当du[i]大于0的时候，st到i连一条流量为du[i]的边。
当du[i]小于0的时候，i到sd连一条流量为-du[i]的边。
最后对（st，sd）求一次最大流即可，当所有附加边全部满流时（即maxflow==所有du[]>0之和），有可行解。
有源汇有上下界可行流
模型:现在的网络有一个源点s和汇点t,求出一个流使得源点的总流出量等于汇点的总流入量,其他的点满足流量守恒,而且每条边的流量满足上界和下界限制.
源点和汇点不满足流量守恒,这让我们很难办,因此我们想办法把问题转化成容易处理的每个点都满足流量守恒的无源汇情况.
为了使源汇点满足流量守恒,我们需要有边流入源点s,有边流出汇点t.注意到源点s的流出量等于汇点t的流入量,我们就可以从汇点t向源点s连一条下界为0上界为无穷大的边,相当于把从源点s流出的流量再流回来.在这样的图中套用上面的算法求出一个可行的循环流,拆掉从汇点t到源点s的边就得到一个可行的有源汇流.
这里有一个小问题:最后得到的可行的有源汇流的流量是多少?
可以发现,循环流中一定满足s流出的总流量=流入s的总流量,假定原图中没有边流入s,那么s流出的流量就是t到s的无穷边的流量,也就是s-t可行流的流量.因此我们最后看一下t到s的无穷边的流量(即dinic跑完之后反向边的权值)即可知道原图中有源汇可行流的流量.
有源汇有上下界最大流
模型:现在的网络有一个源点s和汇点t,求出一个流使得源点的总流出量等于汇点的总流入量,其他的点满足流量守恒,而且每条边的流量满足上界和下界限制.在这些前提下要求总流量最大.
首先套用上面的算法求出一个有源汇有上下界可行流.此时的流不一定最大.
接下来在残量网络上跑s-t最大流即可.
最终的最大流流量=可行流流量(即t到s的无穷边上跑出的流量)+新增广出的s-t流量
问题:会不会增广的时候使得一些边不满足流量下限?
不会.因为我们一开始建的图就是把大小等于流量下限的流量拿出去之后的残量网络,这些流量根本没有在图中出现.
建图模型
源点s，终点d。超级源点ss，超级终点dd。首先判断是否存在满足所有边上下界的可行流，方法可以转化成无源汇有上下界的可行流问题。怎么转换呢？
增设一条从d到s没有下界容量为无穷的边，那么原图就变成了一个无源汇的循环流图。接下来的事情一样，超级源点ss连i（du[i]>0），i连超级汇点（du[i]<0）,
对（ss，dd）进行一次最大流，当maxflow等于所有(du[]>0)之和时，有可行流，否则没有。
当有可行流时，删除超级源点ss和超级终点dd，再对（s，d）进行一次最大流，此时得到的maxflow则为题目的解。为什么呢？因为第一次maxflow（）只是求得所有满足下界的流量，而残留网络（s，d）路上还有许多自由流（没有和超级源点和超级汇点连接的边）没有流满，所有最终得到的maxflow=（第一次流满下界的流+第二次能流通的自由流）。
具体证明：https://blog.csdn.net/axuan_k/article/details/47282421
Fantastic Graph
"Oh, There is a bipartite graph.""Make it Fantastic."
X wants to check whether a bipartite graph is a fantastic graph. He has two fantastic numbers, and he wants to let all the degrees to between the two boundaries. You can pick up several edges from the current graph and try to make the degrees of every point to between the two boundaries. If you pick one edge, the degrees of two end points will both increase by one. Can you help X to check whether it is possible to fix the graph?
Input
There are at most 30 test cases.
For each test case,The first line contains three integers N the number of left part graph vertices, M the number of right part graph vertices, and K the number of edges ( 1≤N≤20001 le N le 2000
1≤N≤2000,0≤M≤20000 le M le 20000≤M≤2000,0≤K≤60000 le K le 60000≤K≤6000 ). Vertices are numbered from 1 to N.
The second line contains two numbers L,R (0≤L≤R≤300)(0 le L le R le 300)(0≤L≤R≤300). The two fantastic numbers.Then K lines follows, each line containing two numbers U, V
(1≤U≤N,1≤V≤M)(1 le U le N,1 le V le M)(1≤U≤N,1≤V≤M). It shows that there is a directed edge from U-th spot to V-th spot.Note. There may be multiple edges between two vertices.
Output
One line containing a sentence. Begin with the case number. If it is possible to pick some edges to make the graph fantastic, output "Yes" (without quote), else output "No" (without quote).
样例输入
3 3 7
2 3
1 2
2 3
1 3
3 2
3 3
2 1
2 1
3 3 7
3 4
1 2
2 3
1 3
3 2
3 3
2 1
2 1
样例输出
Case 1: Yes
Case 2: No
code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+7;
const int maxm=1e5+7;
const int inf=0x3f3f3f3f;
struct Dinic
{
struct Edge
{
int next,f,to;
} e[maxm];
int head[maxn],dep[maxn],tol,ans;
int cur[maxn];
int src,sink,n;
void add(int u,int v,int f)
{
tol++;
e[tol].to=v;
e[tol].next=head[u];
e[tol].f=f;
head[u]=tol;
tol++;
e[tol].to=u;
e[tol].next=head[v];
e[tol].f=0;
head[v]=tol;
}
bool bfs()
{
queue<int>q;
memset(dep,-1,sizeof(dep));
q.push(src);
dep[src]=0;
while(!q.empty())
{
int now=q.front();
q.pop();
for(int i=head[now]; i; i=e[i].next)
{
if(dep[e[i].to]==-1&&e[i].f)
{
dep[e[i].to]=dep[now]+1;
if(e[i].to==sink)
return true;
q.push(e[i].to);
}
}
}
return false;
}
int dfs(int x,int maxx)
{
if(x==sink)
return maxx;
for(int& i=cur[x]; i; i=e[i].next)
{
if(dep[e[i].to]==dep[x]+1&&e[i].f>0)
{
int flow=dfs(e[i].to,min(maxx,e[i].f));
if(flow)
{
e[i].f-=flow;
e[i^1].f+=flow;
return flow;
}
}
}
return 0;
}
int dinic(int s,int t)
{
ans=0;
this->src=s;
this->sink=t;
while(bfs())
{
for(int i=0; i<=n; i++)
cur[i]=head[i];
while(int d=dfs(src,inf))
ans+=d;
}
return ans;
}
void init(int n)
{
this->n=n;
memset(head,0,sizeof(head));
tol=1;
}
}G;
int du[maxn];
int k,sum,Case,l,r,n,m;
int main()
{
while(scanf("%d%d%d",&n,&m,&k)!=EOF){
++Case;
memset(du,0,sizeof(du));
scanf("%d%d",&l,&r);
G.init(n+m+10);
for(int i=1;i<=n;i++){
G.add(0,i,r-l);
du[i]+=l;du[0]-=l;
}
for(int i=1;i<=m;i++){
G.add(i+n,n+m+1,r-l);
du[i+n]-=l;du[n+m+1]+=l;
}
int u,v;sum=0;
for(int i=1;i<=k;i++){
scanf("%d%d",&u,&v);
G.add(u,v+n,1);
}
G.add(n+m+1,0,inf);
int s=n+m+2,t=n+m+3;
for(int i=0;i<=n+m+1;i++){
if(du[i]>0){
sum+=du[i];
G.add(s,i,du[i]);
}
if(du[i]<0){
G.add(i,t,-du[i]);
}
}
int maxflow=G.dinic(s,t);
printf("Case %d: ",Case);
if(maxflow==sum) puts("Yes");
else puts("No");
}
return 0;
}