分析:

  这道题乍一看……卧槽这都什么玩意……

  然后发现给了个A矩阵,要求一个可行的B矩阵,使得矩阵C=A-B的每一行的和的绝对值和每一列的和的绝对值的最大值最小……

  好拗口啊……

  什么最大值最小之类的,考的无非就是二分,我们二分一个答案,之后建图跑网络流。

  因为要判断是否合法,所以我们想到了用有上下界的可行流,在这里我们采用有源汇的有上下界可行流。

  我们把每行建点,第i行为xi,每列建点,第i列为yi,从S点到每行xi代表的点连边,容量为这一行的数值和±mid,从每一列yi代表的点向T点连边,容量为这一列的数值和±mid。(±mid为的是适应绝对值,-mid代表下界,+mid代表上界)

  还要把每一行对应的点xi分别向每一列代表的点yj连边,上下界为L,R,为的是满足B数组的L和R限制,因为在这里,第i行的点到第j列的点连边的流量,表示的就是B矩阵B(i,j)这个位置的值。

  这只是初步建图,我们要跑可行流,还要按要求将图转化,首先T到S连inf边,转化为无源汇上下界可行流。

  然后建出新的S,T点,按照规则将图进行变换。

  二分判定之后最终得出的结果,就是答案。

代码:

 #include<bits/stdc++.h>
#define ms(a,x) memset(a,x,sizeof(a))
using namespace std;
const int N=,M=,inf=0x3f3f3f3f;
struct node{int y,z,nxt;}e[M];int S,T,tot;
int L,R,n,m,a[N][N],sx[N],sy[N],h[N*];
int d[N*],q[N*],t[N*],md,c=,ans;
void add(int x,int y,int z){
e[++c]=(node){y,z,h[x]};h[x]=c;
e[++c]=(node){x,,h[y]};h[y]=c;
} bool bfs(){
int f=,t=;ms(d,-);
q[++t]=S;d[S]=;
while(f<=t){
int x=q[f++];
for(int i=h[x],y;i;i=e[i].nxt)
if(d[y=e[i].y]==-&&e[i].z)
d[y]=d[x]+,q[++t]=y;
} return (d[T]!=-);
} int dfs(int x,int f){
if(x==T) return f;int w,tmp=;
for(int i=h[x],y;i;i=e[i].nxt)
if(d[y=e[i].y]==d[x]+&&e[i].z){
w=dfs(y,min(e[i].z,f-tmp));
if(!w) d[y]=-;e[i].z-=w;
e[i^].z+=w;tmp+=w;
if(tmp==f) return f;
} return tmp;
} void dinic(){
while(bfs()) tot+=dfs(S,inf);
} bool pd(int lim){
ans=tot=;int ad;c=;ms(h,);ms(t,);
md=n+m+;S=;T=md+;
for(int i=;i<=n;i++){
int j=max(,sx[i]-lim);
int k=sx[i]+lim;t[md]-=j;
t[i]+=j;add(md,i,k-j);//构建残量网络
} for(int i=;i<=m;i++){
int j=max(,sy[i]-lim);
int k=sy[i]+lim;t[md]+=j;
t[i+n]-=j;add(i+n,md,k-j);
} for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
t[i]-=L;t[j+n]+=L;
add(i,j+n,R-L);
} for(int i=;i<=md;i++)
if(t[i]){
if(t[i]>) add(S,i,t[i]),
ans+=t[i];else add(i,T,-t[i]);
} dinic();ans-=tot;return !ans;
} int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&a[i][j]),
sx[i]+=a[i][j],sy[j]+=a[i][j];
scanf("%d%d",&L,&R);
int l=,r=2e5,pos;
while(l<=r){
int mid=l+r>>;
if(pd(mid)) pos=mid,r=mid-;
else l=mid+;
} printf("%d\n",pos);
return ;
}

有上下界可行流

最新文章

  1. 【技巧篇】解决悬浮的&lt;header&gt;、&lt;footer&gt;遮挡内容的处理技巧
  2. MySQL数据库原理
  3. 【转】oracle Sequence
  4. yarn安装部署
  5. Google谷歌推出goo.gl缩短网址服务 - Blog透视镜
  6. Linux 内核无线子系统
  7. 在QuartusII 中使用tcl对工程进行复制——半自动
  8. Android4.3引入的UiAutomation新框架官方简介
  9. freemark标签中输出boolean值
  10. django集成celery
  11. AutoMapper入门使用
  12. 运用了css,js
  13. 转 JVM找出占用CPU最高的线程
  14. gcc 与 g++的区分较
  15. Struts2学习笔记(OGNL表达式)
  16. FPGA编码规则检查表
  17. 浏览器环境下的javascript DOM对象继承模型
  18. jQuery筛选器及对DOM修改(学习笔记)
  19. laravel 中的入口文件报错
  20. ubuntu 自动清理/tmp目录

热门文章

  1. 使用 dynamic 标记解析JSON字符串(转)
  2. Linux系统挂载NTFS文件系统(转载)
  3. SQL两个字段排序
  4. Swift4 协议
  5. E20170523-hm
  6. A+B Problem——经典中的经典
  7. Luogu P1004/P1006 方格取数/传纸条 【棋盘Dp】 By cellur925
  8. centos 7更换阿里源
  9. JDK与JRE、JVM三者间的关系及JDK的安装部署
  10. Django 源码安装及使用