Luogu4194 / LOJ115 - 网络流 -

题目链接：https://www.luogu.com.cn/problem/P4194

题解：
LOJ115 是无源汇上下界可行流的板子题 Luogu4194 需要一定建模
无源汇上下界可行流，需要求一张图的流函数，使得满足流量守恒，而且每条边的流量在 \([L,R]\) 之间
那么该如何做呢？首先建一张新图，容量为 \(R-L\) 然后建一个超级源点 \(S\) 超级汇点 \(T\)
对于每条边 \((u,v)\) 设容量为 \(w\) ，那么 \(in[u]-w, out[v]+w\)
然后对于每个点，记 \(delta = in[i] - out[i]\)，如果 \(delta > 0\)，说明这个点能流进来的比较多，\(S \rightarrow i\) 连一条容量为 \(delta\) 的边，否则 \(i \rightarrow T\) 连一条 \(-delta\) 的边，记 \(P = \sum{delta} (如果\ delta > 0)\)
跑一遍最大流，看最大流是否为 \(P\)，如果是说明能在新图中满足流量守恒，就是一个可行流，否则不是
最后对于每条边，\(L + e.flow\) 即为这条边的最终流量，显然 \(\in [L,R]\)
如果有源汇呢？在 原图 的汇点到源点连一条 \(INF\) 的边（注意别溢出了，注意不是超级源点超级汇点），同上

LOJ115 需要输出每一条边的方案，那就每条边记一个编号，其余同理，注意dinic中每条边的 \(flow\) 即为这条边的流量

// by SkyRainWind
// 求有源汇？连一条 T->S c = inf 的边（注意不是超级源汇！） 
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 10005;

int n,m;
struct ed{
	LL from,to,cap,flow,rev;
	int id, low, ad;
	ed(){}
	ed(LL from,LL to,LL cap,LL flow,LL rev,int id,int low,int ad):from(from),to(to),cap(cap),flow(flow),rev(rev),id(id),low(low),ad(ad){}
};
vector<ed>g[maxn];

struct netflow{
	int cur[maxn]; 
	int d[maxn], q[maxn], hd, tl;
	int s, t;	// 源 汇 
	
	netflow(){s=t=-1;}
	
	void init(int s0,int t0){
		s = s0, t = t0;
	}

	void add(int x,int y,LL v,int id,int low,int gg){
		g[x].push_back(ed(x,y,v,0,g[y].size(),id,low,gg));
		g[y].push_back(ed(y,x,0,0,g[x].size() - 1,id,low,0));
	}
	
	int bfs(){
		memset(d,0, sizeof d);
		hd = tl = 0;
		q[tl ++] = s;
		d[s] = 1;
		while(hd != tl){
			int now = q[hd ++];
			for(int i = 0;i<g[now].size();i++){
				ed &e = g[now][i];
				if(!d[e.to] && e.cap > e.flow)d[e.to] = d[now] + 1, q[tl ++] = e.to;
			}
		}
		return d[t];
	}
	
	LL dfs(int now,LL rem){	// rem 当前流量 
		if(now == t || !rem)return rem;
		LL flow = 0;
		for(int &i = cur[now]; i < g[now].size();i ++){
			ed &e = g[now][i];
				// 分层图 & 残量不为0 
			if(d[e.to] == d[now] + 1 && e.cap > e.flow){
				LL f = dfs(e.to, min(rem, e.cap - e.flow));
				rem -= f, flow += f, e.flow += f, g[e.to][e.rev].flow -= f;
			}
			if(!rem)break;
		}
		if(rem)d[now] = -1;
		return flow;
	}
	
	LL dinic(){
		assert(s!=-1);
		LL flow = 0;
		while(bfs()){
			memset(cur, 0, sizeof cur);
			flow += dfs(s, 1ll << 62);
		}
		return flow;
	}
}nf;
int in[maxn], out[maxn], ans[maxn];

signed main(){
	scanf("%d%d",&n,&m);
	int s = 0, t = n+1;
	for(int i=1;i<=m;i++){
		int x, y, lw, up;
		scanf("%d%d%d%d",&x,&y,&lw,&up);
		nf.add(x, y, up - lw, i, lw, 1);
		out[x] += lw;
		in[y] += lw;
	}
	
	int lim = 0;
	for(int i=1;i<=n;i++){
		int cur = in[i] - out[i];
			// id = 0，直接不会纳入最后计算 
		if(cur > 0)nf.add(s, i, cur, 0, 0, 0), lim += cur;
		else nf.add(i, t, -cur, 0, 0, 0);
	}
	nf.init(s, t);
	
	int res = nf.dinic();
//	printf("%d\n",lim);
	if(res < lim)puts("NO");
	else{
		puts("YES");
		for(int i=1;i<=n;i++){
			for(ed e : g[i]){
//				printf("%d\n",e.flow);
				if(e.ad)ans[e.id] = e.low + e.flow;
			}
		}
		for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
	}

	return 0;
}

Luogu4194
首先二分答案，因为A确定，问题就变成了B的每行之和减去A这行和的差的绝对值 < mid，列同理
记A第 \(i\) 行的和为 \(S\) ，那么B的第 \(i\) 行和应该为 \([S-mid, S+mid]\)
注意B中的一个元素会影响一行一列，因此考虑将行和列单独拆开，分别考虑
每行有限制，所以 \(S\rightarrow row_1..\) 的时候容量设为 \([rowsum_1[1]-mid,rowsum_1[1]+mid]\)，其余同理，每列也有限制，同理，只不过是\(colsum\)
每个点的取值也有限制：\([L,R]\)，因此\(row1\)向每个点连的边的容量就是这个，同理这个点向每列连的边也是。流过这个点的流量就是这个点的取值。因为流量守恒，所以这个点的值不变

跑有源汇的上下界可行流即可，INF不要开的太大防止越界（当然可以用ll）

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long LL;

const int inf = 1e9, INF = 2e7, maxn = 1e5+5;

int n,m,a[205][205],srow[maxn],scol[maxn],rowid[maxn],colid[maxn],S,T;
int L,R;
int ind(int x,int y){return (x-1) * m + y;}

struct ed{
	LL from,to,cap,flow,rev;
	ed(){}
	ed(LL from,LL to,LL cap,LL flow,LL rev):from(from),to(to),cap(cap),flow(flow),rev(rev){}
};
vector<ed>g[maxn];

struct netflow{
	int cur[maxn]; 
	int d[maxn], q[maxn], hd, tl;
	int s, t;	// 源 汇 
	
	netflow(){s=t=-1;}
	void clear(){
		s=t=-1;
		for(int i=1;i<=n*m+n+m+10;i++)g[i].clear();
	}
	
	void init(int s0,int t0){
		s = s0, t = t0;
	}

	void add(int x,int y,LL v){
		g[x].push_back(ed(x,y,v,0,g[y].size()));
		g[y].push_back(ed(y,x,0,0,g[x].size() - 1));
	}
	
	int bfs(){
		memset(d,0, sizeof d);
		hd = tl = 0;
		q[tl ++] = s;
		d[s] = 1;
		while(hd != tl){
			int now = q[hd ++];
			for(int i = 0;i<g[now].size();i++){
				ed &e = g[now][i];
				if(!d[e.to] && e.cap > e.flow)d[e.to] = d[now] + 1, q[tl ++] = e.to;
			}
		}
		return d[t];
	}
	
	LL dfs(int now,LL rem){	// rem 当前流量 
		if(now == t || !rem)return rem;
		LL flow = 0;
		for(int &i = cur[now]; i < g[now].size();i ++){
			ed &e = g[now][i];
				// 分层图 & 残量不为0 
			if(d[e.to] == d[now] + 1 && e.cap > e.flow){
				LL f = dfs(e.to, min(rem, e.cap - e.flow));
				rem -= f, flow += f, e.flow += f, g[e.to][e.rev].flow -= f;
			}
			if(!rem)break;
		}
		if(rem)d[now] = -1;
		return flow;
	}
	
	LL dinic(){
		assert(s!=-1);
		LL flow = 0;
		while(bfs()){
			memset(cur, 0, sizeof cur);
			flow += dfs(s, 1ll << 62);
		}
		return flow;
	}
}nf;

int in[maxn], out[maxn], totn;
int check(int mid){
	nf.clear();
	memset(in, 0, sizeof in);memset(out, 0, sizeof out);
	// S -> row[1..n]
	for(int i=1;i<=n;i++){
		nf.add(S, rowid[i], 2 * mid);
		out[S] += (srow[i] - mid);
		in[rowid[i]] += (srow[i] - mid);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			nf.add(rowid[i], ind(i,j), R - L);
			out[rowid[i]] += L;
			in[ind(i, j)] += L;
		}
	}
	
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			nf.add(ind(j, i), colid[i], R - L);
			out[ind(j, i)] += L;
			in[colid[i]] += L; 
		}
	}
	
	for(int i=1;i<=m;i++){
		nf.add(colid[i], T, 2 * mid);
		out[colid[i]] += scol[i] - mid;
		in[T] += scol[i] - mid;
	}
	
	nf.add(T, S, INF);
	out[T] += INF; in[T] += INF;
	
	int SS = totn+1, TT = totn + 2, lim = 0; 
	for(int i=1;i<=totn;i++){
		int cur = in[i] - out[i];
		if(cur > 0)nf.add(SS, i, cur),lim += cur;
		else nf.add(i, TT, -cur);
	}
	nf.init(SS, TT);
	
	int res = nf.dinic();
	if(res < lim)return 0;
	return 1;
}

signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
	scanf("%d%d",&L,&R);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)srow[i] += a[i][j], scol[j] += a[i][j];
	
	S = n*m+1, T = n*m+2;
	for(int i=1;i<=n;i++)rowid[i] = n*m+i+2;
	for(int i=1;i<=m;i++)colid[i] = n*m+n+2+i; 
	totn = n*m+n+2+m;
	
//	printf("! %d\n",check(0));
	int l=0, r = 2e5, ans;
	while(l <= r){
		int mid = l+r>>1;
		if(check(mid))ans = mid, r = mid-1;
		else l = mid+1;
	}
	printf("%d\n",ans);

	return 0;
}