LOJ #116. 有源汇有上下界最大流

我们在源点 (S) 和汇点 (T) 之间连一条上界为 (0) 下界为 (Inf) 的边，转化为无源汇上下界可行流，跑出超级源 (S') 与超级汇 (T') 之间的最大流 (F)。

然后在残量网络上跑 ((S,T)) 的最大流 (f)（尽量填充剩余流量）。

最终答案即为 (F+f) 。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define R register int
using namespace std;
namespace Luitaryi {
inline int g() { R x=0,f=1;
	register char s; while(!isdigit(s=getchar())) f=s=='-'?-1:f;
	do x=x*10+(s^48); while(isdigit(s=getchar())); return x*f;
} const int N=210,M=60010,Inf=0x3f3f3f3f;
int n,m,S,T,s,t,cnt=1,sum;
int vr[M],nxt[M],w[M],fir[N],d[N],cur[N],in[N];
inline void add(int u,int v,int ww) {
	vr[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt,w[cnt]=ww;
	vr[++cnt]=u,nxt[cnt]=fir[v],fir[v]=cnt,w[cnt]=0;
}
queue<int> q;
inline bool bfs() {
	memset(d,0,sizeof d),memcpy(cur,fir,sizeof fir);
	q.push(s),d[s]=1; while(q.size()) { R u=q.front(); q.pop();
		for(R i=fir[u];i;i=nxt[i]) if(w[i]) { R v=vr[i];
			if(!d[v]) d[v]=d[u]+1,q.push(v);
		}
	} return d[t];
}
inline int dfs(int u,int f) {
	if(u==t||f<=0) return f; R res=f;
	for(R& i=cur[u];i;i=nxt[i]) if(w[i]) { R v=vr[i];
		if(d[v]==d[u]+1) {
			R tmp=dfs(v,min(res,w[i]));
			if(!tmp) d[v]=0;
			res-=tmp,w[i]-=tmp,w[i^1]+=tmp;
			if(!res) return f;
		}
	} return f-res;
}
inline int dinic() { R ret=0; 
	while(bfs()) ret+=dfs(s,Inf); return ret;
}
inline void main() {
	n=g(),m=g(),S=g(),T=g(),s=0,t=n+1;
	for(R i=1,u,v,a,b;i<=m;++i) {
		u=g(),v=g(),a=g(),b=g();
		add(u,v,b-a),in[u]-=a,in[v]+=a;
	} for(R i=1;i<=n;++i) 
		if(in[i]<0) add(i,t,-in[i]);
		else add(s,i,in[i]),sum+=in[i];
	add(T,S,Inf); sum-=dinic(); 
	if(sum) return puts("please go home to sleep"),void();
	R tmp=w[cnt]; w[cnt]=w[cnt^1]=0,s=S,t=T;
	printf("%d
",tmp+dinic());
}
} signed main() {Luitaryi::main(); return 0;}

---

2019.12.29