无源汇有上下界可行流

首先要满足流量下界的需求，强行让每条边都流过low的流量，那么每条边只剩下的容量为upp-low，同时设流入点x的流量-流出点x的流量为d[x]。

考虑调整流网络使得流量平衡（让d[x]变为0）1）对于d[x]<0的点，我们希望向x流入-d[x]的流量 2）对于d[x]>0的点，我们希望从x流出d[x]的流量；

因此，考虑新建附源汇点S-T，S指向所有d[x]>0的x，所有d[x]>0的x指向T就能提供像这样调整的“势”。

对流网络跑最大流，如果存在边(S,?,k)或(?,T,k)满足k!=0，则可知无法调整到流量平衡，即不存在可行流。因为sum a[x] (a[x]>0)=sum -a[x] (a[x]<0)，具体操作时，只检差一边就行了。

显然，此时的一条边的可行流量为跑完最大流后所减少的流量（即反边流量）+原来的下界。

#include <bits/stdc++.h>
using namespace std;
const int N=207; 
const int L=30407;
const int inf=0x3f3f3f3f;

int S,T;
int head[N],to[L],cap[L],last[L],cnt=1;
int que[N],lev[N],hd,tl;

inline void add_edge(int x,int y,int c1,int c2=0) {
	to[++cnt]=y,cap[cnt]=c1,last[cnt]=head[x],head[x]=cnt;
	to[++cnt]=x,cap[cnt]=c2,last[cnt]=head[y],head[y]=cnt; 
}
inline bool bfs() {
	memset(lev,0,sizeof lev);
	lev[S]=1;
	que[hd=0,tl=1]=S;
	while(hd<tl) {
		int x=que[++hd];
		for(int i=head[x]; i; i=last[i]) if(cap[i]>0 && !lev[to[i]]) 
			lev[to[i]]=lev[x]+1, que[++tl]=to[i];
	}
	return lev[T]!=0;
}
int dfs(int x,int tf) {
	if(x==T) return tf;
	int tot=0,tmp;
	for(int i=head[x]; i; i=last[i]) if(cap[i]>0 && lev[x]+1==lev[to[i]]) {
		tmp=dfs(to[i],min(tf-tot,cap[i]));
		if(tmp) cap[i]-=tmp,cap[i^1]+=tmp,tot+=tmp;
		if(tot==tf) break;
	}
	if(!tot) lev[x]=-1;
	return tot;
}
int n,m,a[N],low[L]; 
bool check() {
	for(int i=head[S]; i; i=last[i]) 
		if(cap[i]) return false;
	for(int i=head[T]; i; i=last[i])
		if(cap[i^1]) return false;
	return true;
}
void solve() {
	cnt=1;
	memset(a,0,sizeof a);
	memset(head,0,sizeof head);
	for(int i=1,x,y,upp; i<=m; ++i) {
		scanf("%d%d%d%d",&x,&y,&low[i],&upp);
		a[x]-=low[i];
		a[y]+=low[i];
		add_edge(x,y,upp-low[i]);
	}
	int lst=cnt;
	S=n+1, T=n+2;
	for(int i=1; i<=n; ++i) {
		if(a[i]>0) add_edge(S,i,a[i]);
		if(a[i]<0) add_edge(i,T,-a[i]);
	}
	while(bfs()) dfs(S,inf);
	if(!check()) {
		puts("NO");
		return;
	}
	puts("YES"); 
	for(int i=2; i<=lst; i+=2) {
		printf("%d
",cap[i^1]+low[i>>1]);
	}
}

int main() {
	while(~scanf("%d%d",&n,&m)) solve();
	return 0;
}

有源汇有上下界可行流

无源汇的流网络所有点都要满足d[x]=0，这说明它其实是一个“流循环图”。而对于有源汇的合法的流网络，除了d[s]<0，d[t]>0外，其余点满足d[x]=0，并且d[s]=-d[t]，这启发我们加入t到s的一条下界为0，上界为inf的边，这样，图转化为一个“流循环图”，可以借助无源汇的算法调整。

来看下调整后流网络的边t-s，它的反边流量k=与s、t有关的基准流量，即这样的一组调整必然会给s-t的最大流带来k的贡献。答案即为k。

#include <bits/stdc++.h>
using namespace std;

const int N=207; 
const int L=30407;
const int inf=0x3f3f3f3f;

int S,T,s,t;
int head[N],to[L],cap[L],last[L],cnt=1;
int que[N],lev[N],hd,tl;

inline void add_edge(int x,int y,int c1,int c2=0) {
	to[++cnt]=y,cap[cnt]=c1,last[cnt]=head[x],head[x]=cnt;
	to[++cnt]=x,cap[cnt]=c2,last[cnt]=head[y],head[y]=cnt; 
}
inline bool bfs() {
	memset(lev,0,sizeof lev);
	lev[S]=1;
	que[hd=0,tl=1]=S;
	while(hd<tl) {
		int x=que[++hd];
		for(int i=head[x]; i; i=last[i]) if(cap[i]>0 && !lev[to[i]]) 
			lev[to[i]]=lev[x]+1, que[++tl]=to[i];
	}
	return lev[T]!=0;
}
int dfs(int x,int tf) {
	if(x==T) return tf;
	int tot=0,tmp;
	for(int i=head[x]; i; i=last[i]) if(cap[i]>0 && lev[x]+1==lev[to[i]]) {
		tmp=dfs(to[i],min(tf-tot,cap[i]));
		if(tmp) cap[i]-=tmp,cap[i^1]+=tmp,tot+=tmp;
		if(tot==tf) break;
	}
	if(!tot) lev[x]=-1;
	return tot;
}
int n,m,a[N],low[L]; 
bool check() {
	for(int i=head[S]; i; i=last[i]) 
		if(cap[i]) return false;
	for(int i=head[T]; i; i=last[i])
		if(cap[i^1]) return false;
	return true;
}
void solve() {
	cnt=1;
	memset(a,0,sizeof a);
	memset(head,0,sizeof head);
	for(int i=1,x,y,upp; i<=m; ++i) {
		scanf("%d%d%d%d",&x,&y,&low[i],&upp);
		a[x]-=low[i];
		a[y]+=low[i];
		add_edge(x,y,upp-low[i]);
	}
	add_edge(t,s,inf);
	S=n+1, T=n+2;
	for(int i=1; i<=n; ++i) {
		if(a[i]>0) add_edge(S,i,a[i]);
		if(a[i]<0) add_edge(i,T,-a[i]);
	}
	while(bfs()) dfs(S,inf);
	if(!check()) {
		puts("please go home to sleep");
		return;
	}
	printf("%d
",upp[head[s]]);
}

int main() {
	while(~scanf("%d%d%d%d",&n,&m,&s,&t)) 
		solve();
	return 0;
}

有源汇有上下界最大流

接着第二来讲，因此，再将此边即所有与ST关联的边删除，剩下的便是张一般的流网络，k+此时s-t的最大流即为答案。

进一步的，我们可以不必删除t-s边和ST关联的边，直接采用当前流网络的s-t的最大流作为答案。因为1）t-s边的反边的基准流量必然会被增广；2）不可能存在经过S或T的增广路（S的出边、T的入边全部断开）。

#include <bits/stdc++.h>
using namespace std;

const int N=207; 
const int L=30407;
const int inf=0x3f3f3f3f;

int S,T,s,t;
int head[N],to[L],cap[L],last[L],cnt=1;
int que[N],lev[N],hd,tl;

inline void add_edge(int x,int y,int c1,int c2=0) {
	to[++cnt]=y,cap[cnt]=c1,last[cnt]=head[x],head[x]=cnt;
	to[++cnt]=x,cap[cnt]=c2,last[cnt]=head[y],head[y]=cnt; 
}
inline bool bfs() {
	memset(lev,0,sizeof lev);
	lev[S]=1;
	que[hd=0,tl=1]=S;
	while(hd<tl) {
		int x=que[++hd];
		for(int i=head[x]; i; i=last[i]) if(cap[i]>0 && !lev[to[i]]) 
			lev[to[i]]=lev[x]+1, que[++tl]=to[i];
	}
	return lev[T]!=0;
}
int dfs(int x,int tf) {
	if(x==T) return tf;
	int tot=0,tmp;
	for(int i=head[x]; i; i=last[i]) if(cap[i]>0 && lev[x]+1==lev[to[i]]) {
		tmp=dfs(to[i],min(tf-tot,cap[i]));
		if(tmp) cap[i]-=tmp,cap[i^1]+=tmp,tot+=tmp;
		if(tot==tf) break;
	}
	if(!tot) lev[x]=-1;
	return tot;
}
int n,m,a[N],low[L]; 
bool check() {
	for(int i=head[S]; i; i=last[i]) 
		if(cap[i]) return false;
	for(int i=head[T]; i; i=last[i])
		if(cap[i^1]) return false;
	return true;
}
void solve() {
	cnt=1;
	memset(a,0,sizeof a);
	memset(head,0,sizeof head);
	for(int i=1,x,y,upp; i<=m; ++i) {
		scanf("%d%d%d%d",&x,&y,&low[i],&upp);
		a[x]-=low[i];
		a[y]+=low[i];
		add_edge(x,y,upp-low[i]);
	}
	add_edge(t,s,inf);
	S=n+1, T=n+2;
	for(int i=1; i<=n; ++i) {
		if(a[i]>0) add_edge(S,i,a[i]);
		if(a[i]<0) add_edge(i,T,-a[i]);
	}
	while(bfs()) dfs(S,inf);
	if(!check()) {
		puts("please go home to sleep");
		return;
	}
	int ret=0;
	S=s, T=t;
	while(bfs()) ret+=dfs(S,inf);
	printf("%d
",ret);
}

int main() {
	while(~scanf("%d%d%d%d",&n,&m,&s,&t)) 
		solve();
	return 0;
}

有源汇有上下界最小流

直接的做法是s-t的最小流=基准流量k - (t-s的最大流)。此时要注意删除t-s的边（若不删除，则会使得t-s的最大流接近无穷大，成功GG）。

#include <bits/stdc++.h>
#define LL long long 
using namespace std;

const int N=5e4+20;
const int L=2e6+20;
const LL inf=1e15;

int n,m,s,t,d[N];
int S=N-1,T=N-2;
int head[N],cur[N],to[L],last[L],cnt=1;
int que[N],lev[N],hd,tl;
LL upp[L];

inline void add_edge(int x,int y,LL u) {
	to[++cnt]=y,upp[cnt]=u,last[cnt]=head[x],head[x]=cnt;
	to[++cnt]=x,upp[cnt]=0,last[cnt]=head[y],head[y]=cnt; 
}
inline bool bfs() {
	memset(lev,0,(n+2)<<2);
	lev[S]=1;
	que[hd=0,tl=1]=S;
	while(hd<tl) {
		int x=que[++hd];
		for(int i=head[x]; i; i=last[i]) if(upp[i]>0 && !lev[to[i]]) 
			lev[to[i]]=lev[x]+1, que[++tl]=to[i];
	}
	return lev[T]!=0;
}
LL dfs(int x,LL tf) {
	if(x==T) return tf;
	LL tmp;
	for(int &i=cur[x]; i; i=last[i]) if(upp[i]>0 && lev[x]+1==lev[to[i]]) {
		tmp=dfs(to[i],min(tf,upp[i]));
		if(tmp) {
			upp[i]-=tmp;
			upp[i^1]+=tmp;
			return tmp;
		}
	}
	lev[x]=-1;
	return 0;
}
template<typename T> inline void read(T&d) {
	register char ch=getchar(); d=0;
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) d=d*10+ch-'0',ch=getchar();
} 
LL dinic() {
	LL ret=0,tmp;
	while(bfs()) {
		for(int i=0; i<=n+1; ++i) cur[i]=head[i];
		while((tmp=dfs(S,inf))>0) ret+=tmp;
	}
	return ret;
}
int main() {
	read(n);read(m);read(s);read(t);
	for(int i=1,x,y,low,upp; i<=m; ++i) {
		read(x);read(y);read(low);read(upp);
		d[x]-=low;
		d[y]+=low;
		add_edge(x,y,upp-low); 
	}
	S=0, T=n+1;
	add_edge(t,s,inf);
	for(int i=1; i<=n; ++i) {
		if(d[i]>0) add_edge(S,i,d[i]);
		if(d[i]<0) add_edge(i,T,-d[i]);
	}
	dinic();
	for(int i=head[S]; i; i=last[i]) {
		if(upp[i]) {
			puts("please go home to sleep");
			return 0;
		}
	}
	long long st=upp[head[s]];
	upp[head[s]]=0;
	upp[head[t]]=0;
	S=t, T=s;
	printf("%lld
",st-dinic());
	return 0;
}

无源汇有上下界最小费用可行流

干掉下界的时候，把费用先计算上。把超级源超级汇求最大流的一步，换成最小费用最大流即可。即满足合法的前提下，最小化费用。费用就是之前的费用加上这次的费用。

有源汇有上下界最小费用可行流

参考第一到第二的转化，添加边t-s，下界为0，上界为inf，费用为0。然后按照第五进行调整至所有点流量平衡即可。

有源汇有上下界最小费用最大流

似乎直接按照第三改一波。。mf改为mcmf。

有源汇有上下界最小费用最小流

似乎直接按照第四改一波。。~~我也不清楚，因为要减去最多的花费最大费用流？？？~~

参考资料：

学习笔记上下界网络流作者*Miracle*。

网络流常见建模总结作者panda_2134。