本文共 3093 字，大约阅读时间需要 10 分钟。

找一个矩阵$B$使得每个元素都在$[L,R]$内

设矩阵$C=A-B$

最小化$C$的每一列和的绝对值,每一行和的绝对值的最大值

考虑最后的答案是$mid$

那么$C$的每一行$sum{h}_i$绝对值之和,每一列$sum{l}_i$绝对值之和都小于等于$mid$

也就是$|\sum _{j=1}^m{A}_{i,j}-\sum _{j=1}^m{B}_{i,j}|<=mid$

换句话说,我们得到$\sum _{j=1}^m{B}_{i,j}\in [\sum _{j=1}^m{A}_{i,j}-mid,\sum _{j=1}^m{A}_{i,j}+mid]$

对行,列都是类似的这个式子

于是我们发现,虽然最后的答案没有单调性,但是答案的范围有单调性

也就是说如果答案满足$|\sum _{j=1}^m{A}_{i,j}-\sum _{j=1}^m{B}_{i,j}|<=mid$

那么也一定满足$|\sum _{j=1}^m{A}_{i,j}-\sum _{j=1}^m{B}_{i,j}|<=mid+1$

于是我们可以二分这个$mid$,判断每一行每一列的和是否可以在这个范围内

那么为了满足这些限制…我们可以用上下界网络流!!!

新建源点连向每一行,流量为对应的区间

每一列流向新建汇点,流量为对应区间

每一行向每一列连边流量为$[L,R]$,表示在这个格子上填什么数字

都是板子,具体可以看代码了

#include 
   
    using namespace std;#define int long longconst int maxn = 2e5+10;const int inf = 2e9;struct edge{
   	int to,nxt,flow;}d[maxn]; int head[maxn],cnt=1;int in[maxn],out[maxn],n,m,s,t,ss,tt,L,R;int a[209][209],sumh[209],suml[209];void add(int u,int v,int l,int r){
   	l = max(0ll,l);	in[v] += l, out[u] += l;	d[++cnt] = ( edge ){
   v,head[u],r-l},head[u] = cnt;	d[++cnt] = ( edge ){
   u,head[v],0},head[v] = cnt;}int dis[maxn];bool bfs(int s,int t,int mx){
   	for(int i=0;i<=mx;i++)	dis[i] = 0;	queue
    
     q; q.push( s ); dis[s] = 1;	while( !q.empty() )	{
   		int u = q.front(); q.pop();		for(int i=head[u];i;i=d[i].nxt )		{
   			int v = d[i].to;			if( d[i].flow && dis[v]==0 )			{
   				dis[v] = dis[u]+1;	q.push( v );				if( v==t )	return true;			}		}	}	return false;}int dinic(int u,int t,int flow){
   	int res = flow;	if( u==t )	return res;	for(int i=head[u];i && res;i=d[i].nxt )	{
   		int v = d[i].to;		if( d[i].flow && dis[v]==dis[u]+1 )		{
   			int temp = dinic(v,t,min(d[i].flow,res) );			if( temp==0 )	dis[v] = 0;			d[i].flow -= temp, d[i^1].flow += temp;			res -= temp;		}	}	return flow-res;}vector
     
      vec[maxn];bool isok(int lim){
   	s = n+m+1, t = s+1, ss = t+1, tt = ss+1;	for(int i=1;i<=n;i++)	for(int j=1;j<=m;j++)		add(i,n+j,L,R);	for(int i=1;i<=n;i++)	add(s,i,sumh[i]-lim,sumh[i]+lim);	for(int i=1;i<=m;i++)	add(i+n,t,suml[i]-lim,suml[i]+lim);	add(t,s,0,inf);	int ans = 0;	for(int i=1;i<=t;i++)	{
   		if( in[i]>out[i] )	add(ss,i,0,in[i]-out[i]),ans += in[i]-out[i];		else	add(i,tt,0,out[i]-in[i]);	}	while( bfs(ss,tt,tt) )	ans -= dinic(ss,tt,inf);	cnt = 1;	for(int i=1;i<=tt;i++)	head[i] = in[i] = out[i] = 0;	return ans==0;}signed main(){
   	cin >> n >> m;	for(int i=1;i<=n;i++)	for(int j=1;j<=m;j++)	{
   		cin >> a[i][j];		sumh[i] += a[i][j],suml[j] += a[i][j];	}	cin >> L >> R ;	int l = 0, r = 1e8, ans = 0;	while( r>=l )	{
   		int mid = ( l+r ) >> 1;		if( isok(mid) )	r = mid-1, ans = mid;		else	l = mid+1;	}	cout << ans;}
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/115427581 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！