直接求不好求想到网络流模型，对每行每列算和，二分答案，对每行建点xi，每列建点yi，从s到xi连[sum-mid,sum+mid]边，对每列yi到t连[sum-mid,sum+mid]边，代表行的点和代表列的点连[L,R]的边，跑上下界可行流（注释部分为求方案）。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; queue<int> q; const int inf=0x7f7f7f7f; int read() { char ch=getchar();int f=0; while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){f=(f<<1)+(f<<3)+ch-'0';ch=getchar();} return f; } int a[205][205],n,m,h[505],l[505],L,R,ans[505][505],s,t,ss,tt,temp,cur[505]; struct node { int from; int to; int next; int w; }edge[500005]; int head[505],tot,dis[505]; void add(int u,int v,int w) { edge[tot].from=u; edge[tot].to=v; edge[tot].next=head[u]; edge[tot].w=w; head[u]=tot++; } void ins(int u,int v,int low,int high) { if(low>0) { add(ss,v,low); add(v,ss,0); add(u,tt,low); add(tt,u,0); add(u,v,high-low); add(v,u,0); } else { add(u,v,high); add(v,u,0); } } bool bfs() { q.push(ss); memset(dis,-1,sizeof(dis)); dis[ss]=0; while(!q.empty()) { int x=q.front(); q.pop(); for(int i=head[x];i!=-1;i=edge[i].next) { if(edge[i].w&&dis[edge[i].to]==-1) { dis[edge[i].to]=dis[x]+1; q.push(edge[i].to); } } } if(dis[tt]==-1) return 0; return 1; } int dfs(int x,int flow) { if(x==tt||!flow) { return flow; } int ret=0; for(int i=cur[x];i!=-1;i=edge[i].next) { if(dis[edge[i].to]==dis[x]+1) { int f=dfs(edge[i].to,min(flow,edge[i].w)); edge[i].w-=f;edge[i^1].w+=f; if(edge[i].w) cur[x]=i; ret+=f;flow-=f; if(!flow) break; } } if(!ret) dis[x]=-1; return ret; } void dinic() { temp=0; while(bfs()) { for(int i=0;i<=n+m+10;i++) cur[i]=head[i]; temp+=dfs(ss,0x7f7f7f7f); } } bool check(int mid) { tot=0; memset(head,-1,sizeof(head)); for(int i=1;i<=n;i++) { ins(s,i,h[i]-mid,h[i]+mid); } for(int i=1;i<=m;i++) { ins(i+n,t,l[i]-mid,l[i]+mid); } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { ins(i,j+n,L,R); } } ins(t,s,0,0x7f7f7f7f); dinic(); for(int i=0;i<tot;i++) { if((edge[i].from==ss||edge[i].to==tt)&&edge[i].w) return 0; if((edge[i].from>=1&&edge[i].from<=n&&edge[i].to>=n+1&&edge[i].to<=n+m)) ans[edge[i].from][edge[i].to]=L+edge[i].w; } return 1; } int find() { int left=0,right=2000000,mid,an=2000000; while(left<=right) { mid=left+right>>1; if(check(mid)) { an=mid,right=mid-1; } else left=mid+1; } return an; } int main() { n=read(),m=read(); 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++) { a[i][j]=read(); h[i]+=a[i][j]; l[j]+=a[i][j]; } } L=read(),R=read(); int minans=find(); cout<<minans<<endl; for(int i=0;i<tot;i++) { if((edge[i].to>=1&&edge[i].to<=n&&edge[i].from>=n+1&&edge[i].from<=n+m)) ans[edge[i].to][edge[i].from-n]=L+edge[i].w; } /*for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { printf("%d ",ans[i][j]); } printf("\n"); }*/ }