Description：

给定一个 $n\times m$ 的整数矩阵 $A[][]$ ，求一个矩阵 $B[][]$ 满足 $B[i][j]\in[L,R]$ 且使得下式值最小。 $$ \max \bigg(\max_{1\leqslant j\leqslant m}(\bigg|\sum_{i=1}^n(A_{i,j}-B_{i,j})\bigg|),\max_{1\leqslant j\leqslant m}(\bigg|\sum_{i=1}^n(A_{i,j}-B_{i,j})\bigg|)\bigg) $$ $1\leqslant n\leqslant 200$

Solution：

首先最大值最小可以想到二分，中间那个 $\sum$ 可以拆开，再把绝对值拆了之后就是一个对行的和或者列的和的一个上下界限制，那么我们可以建一个二分图，左部点代表行，右部点代表列，用上下界限制行或者列的和，中间的边代表这个点，也用上下界限制 $[L,R]$ ，判断是否有可行流就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 210

int L,R;

int A[MAXN][MAXN];

int S1[MAXN],S2[MAXN];

int s,t,ss,tt;

#define N 1000000

#define MAXP (MAXN + MAXN)

struct edge

{

	int to,nxt,f;

}e[(MAXN * MAXN + 2 * MAXN) * 2];

int edgenum = 0;

int lin[MAXP];

int ind[MAXP];

void add(int a,int b,int f)

{//cout << a << " -> " << b << " : " << f << endl;

	e[edgenum] = (edge){b,lin[a],f};lin[a] = edgenum++;

	e[edgenum] = (edge){a,lin[b],0};lin[b] = edgenum++;

	return;

}

void adde(int a,int b,int l,int h)

{//cout << a << " " << b << " " << l << " " << h << endl;

	add(a,b,h - l);

	ind[b] += l;ind[a] -= l;

	return;

}

int ch[MAXP];

bool BFS()

{

	memset(ch,-1,sizeof(ch));ch[s] = 0;

	queue<int> q;q.push(s);

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(ch[e[i].to] == -1 && e[i].f)

			{

				ch[e[i].to] = ch[k] + 1;

				q.push(e[i].to);

			}

		}

	}

	return (ch[t] != -1);

}

int flow(int k,int f)

{

	if(k == t)return f;

	int r = 0;

	for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)

	{

		if(ch[e[i].to] == ch[k] + 1 && e[i].f)

		{

			int l = flow(e[i].to,min(e[i].f,f - r));

			e[i].f -= l;r += l;e[i ^ 1].f += l;

		}

	}

	if(r == 0)ch[k] = -1;

	return r;

}

#define INF 0x3f3f3f3f

int dinic()

{

	int ans = 0,r;

	while(BFS())while(r = flow(s,INF))ans += r;//cout << ans << endl;

	return ans;

}

bool check(int lim)

{//cout << lim << endl;

	edgenum = 0;

	memset(lin,-1,sizeof(lin));

	memset(ind,0,sizeof(ind));

	ss = n + m + 1;tt = ss + 1;s = tt + 1;t = s + 1;

	for(int i = 1;i <= n;++i)adde(ss,i,max(S1[i] - lim,0),min(S1[i] + lim,N));

	for(int i = 1;i <= m;++i)adde(i + n,tt,max(S2[i] - lim,0),min(S2[i] + lim,N));

	for(int i = 1;i <= n;++i)for(int j = 1;j <= m;++j)adde(i,j + n,L,R);

	add(tt,ss,INF);

	int sum = 0;

	for(int i = 1;i <= tt;++i)

	{

		if(ind[i] > 0)add(s,i,ind[i]),sum += ind[i];

		else add(i,t,-ind[i]);

	}

	return (dinic() == sum);

}

int 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]);

	for(int i = 1;i <= n;++i)for(int j = 1;j <= m;++j)S1[i] += A[i][j],S2[j] += A[i][j];

	scanf("%d%d",&L,&R);

	int l = 0,r = N,mid;

	while(l < r)

	{

		mid = ((l + r) >> 1);

		if(check(mid))r = mid;

		else l = mid + 1;

	}

	cout << l << endl;

	return 0;

}