苏州 网站建设/seo网站关键字优化

题目：

我是超链接

题解：

题面不是人看的系列
构造一个b矩阵，其中每一个点有限制[L,R]，令矩阵c=a-b，使c矩阵每一行的和的绝对值和每一列的和的绝对值的最大值最小
这种矩阵转化的模型我也写过，看看数据范围大概也猜得到【网络瘤】
但是什么都没有啊，流量？限制？和？
那就先考虑另一个【模型】：最大值最小，二分。
这个矩形的和似乎也可以转化了，我们画一下柿子（以列为例

$|\sum_{j=1}^m a_{ij}-\sum_{j=1}^m b_{ij}|<=mid$

去掉绝对值：$-mid<=\sum_{j=1}^m a_{ij}-\sum_{j=1}^m b_{ij}<=mid$

把已知的a移到两边去$-\sum_{j=1}^m a_{ij}-mid<=-\sum_{j=1}^m b_{ij}<=-\sum_{j=1}^m a_{ij}+mid$

去负号 $\sum_{j=1}^m a_{ij}-mid<=\sum_{j=1}^m b_{ij}<=\sum_{j=1}^m a_{ij}+mid$

诶？这不是我们熟悉的【矩阵的和】吗，那个大于等于小于等于不就是上下界？

裸的有源汇上下界可行流出现了！
但是我把up，down读反了就很GG了

代码：

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define INF 1e9
const int N=100000;
int tot,up,down,n,m,point[N],nxt[N],v[N],remind[N],dis[N],cur[N],d[N],s,t,ss,tt,ll[N],hh[N];
void clear()
{tot=-1;memset(point,-1,sizeof(point));memset(d,0,sizeof(d));
}
void addline(int x,int y,int cap)
{++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; remind[tot]=cap;++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; remind[tot]=0;
}
int dfs(int now,int t,int limit)
{if (now==t || !limit) return limit;int flow=0,f;for (int i=cur[now];i!=-1;i=nxt[i]){cur[now]=i;if (dis[v[i]]==dis[now]+1 && (f=dfs(v[i],t,min(limit,remind[i])))){limit-=f;flow+=f;remind[i]-=f;remind[i^1]+=f;if (!limit) break;}}return flow;
}
bool bfs(int s,int t)
{queue<int>q;memset(dis,0x7f,sizeof(dis));dis[s]=0;for (int i=1;i<=t;i++) cur[i]=point[i];q.push(s);while (!q.empty()){int x=q.front(); q.pop();for (int i=point[x];i!=-1;i=nxt[i])if (dis[v[i]]>INF && remind[i]){dis[v[i]]=dis[x]+1;q.push(v[i]);}}return dis[t]<INF;
}
bool check(int mid)
{clear();for (int i=1;i<=n;i++) {int low=hh[i]-mid,on=hh[i]+mid;low=max(low,0);addline(s,i,on-low);d[s]-=low,d[i]+=low;}for (int i=1;i<=m;i++) {int low=ll[i]-mid,on=ll[i]+mid;low=max(low,0);addline(i+n,t,on-low);d[i+n]-=low,d[t]+=low;}for (int i=1;i<=n;i++)for (int j=1;j<=m;j++) addline(i,j+n,up-down),d[i]-=down,d[j+n]+=down;int in=0,out=0;for (int i=1;i<=t;i++){if (d[i]>0) addline(ss,i,d[i]),in+=d[i];if (d[i]<0) addline(i,tt,-d[i]),out-=d[i];}addline(t,s,INF);int maxflow=0;if (in!=out) return 0;while (bfs(ss,tt)) maxflow+=dfs(ss,tt,INF);if (maxflow!=in) return 0;return 1;
}
int main()
{int a;scanf("%d%d",&n,&m);for (int i=1;i<=n;i++)for (int j=1;j<=m;j++) scanf("%d",&a),hh[i]+=a,ll[j]+=a;scanf("%d%d",&down,&up);s=n+m+1; t=s+1; ss=t+1; tt=ss+1;int l=0,r=250000,ans;while (l<=r){int mid=(l+r)>>1;if (check(mid)) ans=mid,r=mid-1;else l=mid+1;}printf("%d",ans);
}