题目描述
输入
第一行两个数n、m,表示矩阵的大小。
接下来n行,每行m列,描述矩阵A。
最后一行两个数L,R。
输出
第一行,输出最小的答案;
样例输入
2 20 1
2 1
0 1
样例输出
1提示
对于100%的数据满足N,M<=200,0<=L<=R<=1000,0<=Aij<=1000
要求最大值最小,显然二分答案。
每次二分一个$mid$,设每行或每列的$A$之和为$VA$,$B$之和为$VB$,那么就要求每行或每列的$VA-mid\le VB\le VA+mid$,判断是否有可行解。
将源点与每行连边,流量上下界为$[VA-mid,VA+mid]$;每列与汇点连边,流量上下界为$[VA-mid,VA+mid]$;每行与每列连边,流量上下界为$[L,R]$。
每次二分跑一遍有源汇的上下界可行流判断是否满流即可。
注意$VA-mid$要与$0$取$max$。
如果输出方案的话,$b_{ij}$就是$L$加上第$i$行的点向第$j$列的点连的边的反向边流量。
#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<vector> #include<cstdio> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; int head[500]; int low[500]; int to[200010]; int val[200010]; int next[200010]; int tot=1; int n,m; int L,R; int a[210][210]; int b[210][210]; int q[500]; int S,T; int SS,TT; int d[500]; int fx[210]; int fy[210]; int ans; void add(int x,int y,int z) { tot++; next[tot]=head[x]; head[x]=tot; to[tot]=y; val[tot]=z; tot++; next[tot]=head[y]; head[y]=tot; to[tot]=x; val[tot]=0; } bool bfs(int S,int T) { memset(d,-1,sizeof(d)); int l=0; int r=0; d[S]=0; q[r++]=S; while(l<r) { int now=q[l]; l++; for(int i=head[now];i;i=next[i]) { if(d[to[i]]==-1&&val[i]) { d[to[i]]=d[now]+1; q[r++]=to[i]; } } } return d[T]!=-1; } int dfs(int x,int maxflow) { if(x==TT) { return maxflow; } int used=0; int nowflow; for(int i=head[x];i;i=next[i]) { if(d[to[i]]==d[x]+1&&val[i]) { nowflow=dfs(to[i],min(val[i],maxflow-used)); val[i]-=nowflow; val[i^1]+=nowflow; used+=nowflow; if(nowflow==maxflow) { return maxflow; } } } if(!used) { d[x]=-1; } return used; } int dinic() { int res=0; while(bfs(SS,TT)) { res+=dfs(SS,0x3f3f3f3f); } return res; } bool check(int lim) { int res=0; tot=1; memset(head,0,sizeof(head)); memset(low,0,sizeof(low)); add(T,S,1<<30); int sx,sy; for(int i=1;i<=n;i++) { sx=max(fx[i]-lim,0); sy=fx[i]+lim; add(S,i,sy-sx); low[S]-=sx,low[i]+=sx; } for(int i=1;i<=m;i++) { sx=max(fy[i]-lim,0); sy=fy[i]+lim; add(n+i,T,sy-sx); low[n+i]-=sx,low[T]+=sx; } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { add(i,n+j,R-L); low[i]-=L,low[n+j]+=L; } } for(int i=1;i<=T;i++) { if(low[i]>0) { add(SS,i,low[i]); res+=low[i]; } else { add(i,TT,-low[i]); } } return res==dinic(); } int main() { scanf("%d%d",&n,&m); 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++) { scanf("%d",&a[i][j]); fx[i]+=a[i][j],fy[j]+=a[i][j]; } } scanf("%d%d",&L,&R); int l=0,r=200000; while(l<=r) { int mid=(l+r)>>1; if(check(mid)) { ans=mid,r=mid-1; } else { l=mid+1; } } printf("%d\n",ans); // check(ans); // for(int i=1;i<=n;i++) // { // for(int j=head[i];j;j=next[j]) // { // if(to[j]>n&&to[j]<=n+m) // { // b[i][to[j]-n]=L+val[j^1]; // } // } // } // for(int i=1;i<=n;i++) // { // for(int j=1;j<=m;j++) // { // printf("%d",b[i][j]); // if(j!=m) // { // printf(" "); // } // } // printf("\n"); // } }