有上下界的网络流&费用流消圈算法

无源汇可行流

就是一个网络，每条边有一个流量的下限和上限，要求给每条边安排一个流量，使得所有点进出的流量相同。
考虑强制让下限流满，这样必定会造成点的出入流量不平衡，这个问题可以通过建源点汇点来解决。
具体做法是把每条边容量设为上限-下限的值，然后对每个点计算出流入的边的下限之和-流出的边的下限之和的值。如果这个值是正的，就从源点向它连一条容量为这个值的边，表示强制在自由流量中，出的流量比入的流量多这么多；否则向汇点连相反数的容量的边，意义类似。最后跑最大流，判断一下是否每条从源点连出去的边都流满即可。
loj有模板题。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mxn=65536;
int N,M,S,T,head[mxn],cur[mxn],gap[mxn],dep[mxn];
struct ed{int to,nxt,val;}edge[mxn];
void addedge(int u,int v,int w){
	edge[++M]=(ed){v,head[u],w},head[u]=M;
	edge[++M]=(ed){u,head[v],0},head[v]=M;
}
int dfs(int u,int mx){
	if (u==T) return mx;
	int num=0;
	for (int &i=cur[u],v;i;i=edge[i].nxt)
		if (dep[v=edge[i].to]==dep[u]-1&&edge[i].val){
			int f=dfs(v,min(mx-num,edge[i].val));
			edge[i].val-=f,edge[i^1].val+=f,num+=f;
			if (num==mx) return num;
		}
	if (!--gap[dep[u]++]) dep[S]=N+1;
	++gap[dep[u]],cur[u]=head[u];
	return num;
}
int solve(){
	gap[1]=N;
	for (int i=1;i<=N;++i)
		dep[i]=1,cur[i]=head[i];
	int sum=0;
	for (;dep[S]<=N;sum+=dfs(S,0x3f3f3f3f));
	return sum;
}
int n,m,w[mxn],id[mxn],rb[mxn];
void sol(){
	solve();
	for (int i=head[S];i;i=edge[i].nxt)
		if (edge[i].val) return (void)puts("NO");
	puts("YES");
	for (int i=1;i<=m;++i)
		printf("%d
",rb[i]-edge[id[i]].val);
}
int main()
{
	scanf("%d%d",&n,&m);
	N=n+2,M=1,S=n+1,T=N;
	for (int i=1;i<=m;++i){
		int x,y,l,r;
		scanf("%d%d%d%d",&x,&y,&l,&r);
		addedge(x,y,r-l);
		w[x]-=l,w[y]+=l;
		id[i]=M-1,rb[i]=r;
	}
	for (int i=1;i<=n;++i)
		if (w[i]>0) addedge(S,i,w[i]);
		else addedge(i,T,-w[i]);
	sol();
	return 0;
}

有源汇可行流

类似于上一个问题，图中有源点汇点，源点可以多流出一点，汇点可以多流入一点。
显然源点流出的量=汇点流入的量，从汇点到源点连一条容量为正无穷的边就可以转化为无源汇可行流。

有源汇最大流

相当于满足了下限，然后在自由流量上调整，使得流量最大。
所以先求出一个可行流，然后去掉加上去的那条正无穷的边，从原图的源点到汇点跑最大流即可。
loj有模板题。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mxn=100010,inf=0x3f3f3f3f;
int N,M,S,T,head[mxn],cur[mxn],dep[mxn],gap[mxn];
struct ed{int to,nxt,val;}edge[mxn<<1];
void addedge(int u,int v,int w){
	edge[++M]=(ed){v,head[u],w},head[u]=M;
	edge[++M]=(ed){u,head[v],0},head[v]=M;
}
int dfs(int u,int mx){
	if (u==T) return mx;
	int num=0;
	for (int &i=cur[u],v;i;i=edge[i].nxt)
		if (dep[v=edge[i].to]==dep[u]-1&&edge[i].val){
			int f=dfs(v,min(mx-num,edge[i].val));
			edge[i].val-=f,edge[i^1].val+=f,num+=f;
			if (num==mx) return num;
		}
	if (!--gap[dep[u]++]) dep[S]=N+1;
	++gap[dep[u]],cur[u]=head[u];
	return num;
}
int solve(){
	gap[1]=N;
	for (int i=1;i<=N;++i)
		dep[i]=1,cur[i]=head[i];
	int sum=0;
	for (;dep[S]<=N;sum+=dfs(S,inf));
	return sum;
}
int n,m,s,t,w[mxn];
void sol(){
	scanf("%d%d%d%d",&n,&m,&s,&t);
	N=n+2,M=1,S=n+1,T=N;
	for (int i=1;i<=m;++i){
		int x,y,l,r;
		scanf("%d%d%d%d",&x,&y,&l,&r);
		addedge(x,y,r-l);
		w[x]-=l,w[y]+=l;
	}
	for (int i=1;i<=n;++i)
		if (w[i]>0) addedge(S,i,w[i]);
		else addedge(i,T,-w[i]);
	addedge(t,s,inf);
	solve();
	for (int i=head[S];i;i=edge[i].nxt)
		if (edge[i].val) return (void)puts("please go home to sleep");
	int ans=edge[M].val;
	edge[M].val=edge[M^1].val=0;
	S=s,T=t;
	ans+=solve();
	printf("%d
",ans);
}
int main()
{
	sol();
	return 0;
}

有源汇最小流

相当于要在自由网络上退回最多的流量，求出可行流，去掉那条边之后ans-=从原图汇点到源点的最大流即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int rd(){
	int x=0;
	char c=getchar();
	for (;c<48||c>57;c=getchar());
	for (;c>47&&c<58;x=x*10+c-48,c=getchar());
	return x;
}
const int mxn=500010,inf=2147483647;
int N,M,S,T,head[mxn],cur[mxn],dep[mxn],gap[mxn];
struct ed{int to,nxt,val;}edge[mxn<<1];
void addedge(int u,int v,int w){
	edge[++M]=(ed){v,head[u],w},head[u]=M;
	edge[++M]=(ed){u,head[v],0},head[v]=M;
}
int dfs(int u,int mx){
	if (u==T) return mx;
	int num=0;
	for (int &i=cur[u],v;i;i=edge[i].nxt)
		if (edge[i].val&&dep[v=edge[i].to]==dep[u]-1){
			int f=dfs(v,min(mx-num,edge[i].val));
			edge[i].val-=f,edge[i^1].val+=f,num+=f;
			if (num==mx) return num;
		}
	if (!--gap[dep[u]++]) dep[S]=N+1;
	++gap[dep[u]],cur[u]=head[u];
	return num;
}
int solve(){
	gap[1]=N;
	for (int i=1;i<=N;++i)
		dep[i]=1,cur[i]=head[i];
	int sum=0;
	for (;dep[S]<=N;sum+=dfs(S,inf));
	return sum;
}
int n,m,s,t,w[mxn];
void sol(){
	n=rd(),m=rd(),s=rd(),t=rd();
	N=n+2,M=1,S=n+1,T=N;
	for (int i=1;i<=m;++i){
		int x=rd(),y=rd(),l=rd(),r=rd();
		addedge(x,y,r-l);
		w[x]-=l,w[y]+=l;
	}
	for (int i=1;i<=n;++i)
		if (w[i]>0) addedge(S,i,w[i]);
		else addedge(i,T,-w[i]);
	addedge(t,s,inf);
	solve();
	for (int i=head[S];i;i=edge[i].nxt)
		if (edge[i].val) return (void)puts("please go home to sleep");
	int ans=edge[M].val;
	edge[M].val=edge[M^1].val=0;
	S=t,T=s;
	ans-=solve();
	printf("%d
",ans);
}
int main()
{
	sol();
	return 0;
}

有源汇最小费用可行流

和有源汇可行流不是一样的吗。。。
模板提bzoj3876

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mxn=16384,inf=0x3f3f3f3f;
int N,M,S,T,dst,sum,flw,head[mxn],dis[mxn],vis[mxn],q[mxn];
struct ed{int to,nxt,val,fee;}edge[mxn];
void addedge(int u,int v,int w,int f){
    edge[++M]=(ed){v,head[u],w,f},head[u]=M;
    edge[++M]=(ed){u,head[v],0,-f},head[v]=M;
}
int dfs(int u,int mx){
    if (u==T) return sum+=dst*mx,mx;
    int num=0;
    vis[u]=1;
    for (int i=head[u],v;i;i=edge[i].nxt)
        if (!vis[v=edge[i].to]&&!edge[i].fee&&edge[i].val){
            int f=dfs(v,min(mx-num,edge[i].val));
            edge[i].val-=f,edge[i^1].val+=f,num+=f;
            if (num==mx) return vis[u]=0,num;
        }
    return num;
}
bool bfs(){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    q[1]=T,dis[T]=0;
    for (int hd=0,tl=1;hd!=tl;){
        int u=q[hd=hd%N+1];
        vis[u]=0;
        for (int i=head[u],v;i;i=edge[i].nxt)
            if (dis[v=edge[i].to]>dis[u]-edge[i].fee&&edge[i^1].val){
                dis[v]=dis[u]-edge[i].fee;
                if (!vis[v]){
                    vis[v]=1;
                    if (hd!=tl&&dis[q[hd+1]]>dis[v]) q[hd]=v,hd=hd-1+(hd<2)*N;
                    else q[tl=tl%N+1]=v;
                }
            }
    }
    for (int u=1;u<=N;++u)
        for (int i=head[u];i;i=edge[i].nxt)
            edge[i].fee-=dis[u]-dis[edge[i].to];
    dst+=dis[S];
    return dis[S]<inf;
}
void solve(){
    for (;bfs();flw+=dfs(S,inf));
}
int n,m,s,t,ans,w[mxn];
int main()
{
    scanf("%d",&n);
    s=n+1,t=n+2;
    N=t+2,M=1,S=t+1,T=N;
    addedge(s,1,inf,0);
    for (int i=1;i<=n;++i) addedge(i,t,inf,0);
    for (int i=1;i<=n;++i){
        scanf("%d",&m);
        for (int j=1,x,y;j<=m;++j){
            scanf("%d%d",&x,&y);
            addedge(i,x,inf,y);
            --w[i],++w[x];
            ans+=y;
        }
    }
    for (int i=1;i<=t;++i)
        if (w[i]>0) addedge(S,i,w[i],0);
        else addedge(i,T,-w[i],0);
    addedge(t,s,inf,0);
    solve();
    ans+=sum;
    printf("%d
",ans);
    return 0;
}

费用流消圈算法

GDSOI2019D1T4，一道上下界费用流模板题，但是。。。有负环。
基于spfa的费用流肯定是不适用的，这里介绍一种消圈求费用流的算法。
首先求出最大流，这时候原图不存在增广路，想要求出更优解，增广的过程肯定是一个负环。
所以每次找出一个负环，手动把流量修改一下就可以了。
注意判负环时找到的那一个点不一定在负环上，所以要记一个(pre)，每次往前跳直到跳到已经跳过的点为止。
复杂度不知道，反正很慢。
这题自己构造的数据跑了4s，不过用spfa判环应该就不会这么慢了？

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mxn=16384,inf=0x3f3f3f3f;
int N,M,S,T,dst,sum,flw,head[mxn],cur[mxn],dep[mxn],gap[mxn];
struct ed{int to,nxt,val,fee;}edge[mxn];
void addedge(int u,int v,int w,int f){
	edge[++M]=(ed){v,head[u],w,f},head[u]=M;
	edge[++M]=(ed){u,head[v],0,-f},head[v]=M;
}
int dfs(int u,int mx){
	if (u==T) return mx;
	int num=0;
	for (int &i=cur[u],v;i;i=edge[i].nxt)
		if (dep[v=edge[i].to]==dep[u]-1&&edge[i].val){
			int f=dfs(v,min(mx-num,edge[i].val));
			edge[i].val-=f,edge[i^1].val+=f,num+=f;
			if (num==mx) return num;
		}
	if (!--gap[dep[u]++]) dep[S]=N+1;
	++gap[dep[u]],cur[u]=head[u];
	return num;
}
int MaxFlow_solve(){
	gap[1]=N;
	for (int i=1;i<=N;++i)
		dep[i]=1,cur[i]=head[i];
	int flw=0;
	for (;dep[S]<=N;flw+=dfs(S,inf));
	return flw;
}
int dis[mxn],pre[mxn];
int check(){
	memset(dis,0,sizeof(dis));
	for (int i=1;i<N;++i)
		for (int j=2;j<=M;++j)
			if (edge[j].val){
				int u=edge[j^1].to,v=edge[j].to,w=edge[j].fee;
				if (dis[v]>dis[u]+w) dis[v]=dis[u]+w,pre[v]=j;
			}
	for (int j=2;j<=M;++j)
		if (edge[j].val){
			int u=edge[j^1].to,v=edge[j].to,w=edge[j].fee;
			if (dis[v]>dis[u]+w) return v;
		}
	return 0;
}
void upd(int i){
	int fl=inf;
	for (int j=i;;){
		fl=min(fl,edge[j].val);
		j=pre[edge[j^1].to];
		if (j==i) break;
	}
	for (int j=i;;){
		edge[j].val-=fl,edge[j^1].val+=fl;
		j=pre[edge[j^1].to];
		if (j==i) break;
	}
}
int solve(){
	for (int u=check();u;u=check()){
		for (;dis[u]<=0;dis[u]=1,u=edge[pre[u]^1].to);
		upd(pre[u]);
	}
	int sum=0;
	for (int i=3;i<=M;i+=2)
		sum-=edge[i].val*edge[i].fee;
	return sum;
}
int n,m,k,s,t,sa,sb,a[64][64];
int main()
{
	freopen("in.txt","r",stdin);
	scanf("%d%d%d",&n,&m,&k);
	s=n+m+1,t=n+m+2;
	N=n+m+4,M=1,S=N-1,T=N;
	for (int i=1,l,r;i<=n;++i){
		scanf("%d%d",&l,&r);
		addedge(s,i,r-l,0);
		addedge(S,i,l,0);
		sa+=l;
	}
	for (int i=1,l,r;i<=m;++i){
		scanf("%d%d",&l,&r);
		addedge(n+i,t,r-l,0);
		addedge(n+i,T,l,0);
		sb+=l;
	}
	addedge(s,T,sa,0);
	addedge(S,t,sb,0);
	for (int i=1,x,y;i<=k;++i)
		scanf("%d%d",&x,&y),a[x][y]=1;
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j)
			if (!a[i][j]) addedge(i,n+j,1,1);
			else addedge(i,n+j,1,-1);
	addedge(t,s,inf,0);
	MaxFlow_solve();
	k+=solve();
	printf("%d
",k);
	return 0;
}