bzoj千题计划158:bzoj2406: 矩阵(有源汇上下界可行流)

http://www.lydsy.com/JudgeOnline/problem.php?id=2406

bzoj千题计划158:bzoj2406: 矩阵(有源汇上下界可行流)

设矩阵C=A-B

最小化 C 一行或一列和的最大值

整体考虑一行或者一列的和

二分最大值

这样每一行一列的和就有了范围

|Σai-Σbj|<=mid

去掉绝对值 Σai-mid <= Σbi <= Σai+mid

构图:

源点向行连下界为Σai-mid,上界为 Σai+mid 的边

列向汇点连下界为Σai-mid,上界为 Σai+mid 的边

第i行向第j列连下界为L,上界为R的边

上下界可行流验证

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> #define N 405
#define M 41000 const int inf=2e9; int n,m,L,R; int sumh[N],suml[N]; int s,t,S,T; int d[N]; int SUM; int front[N],to[M<<],nxt[M<<],tot,val[M<<]; int lev[N],cur[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void add(int u,int v,int w)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; val[tot]=w;
to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; val[tot]=;
//printf("%d %d %d\n",u,v,w);
} void build(int mid)
{
tot=;
memset(front,,sizeof(front));
memset(d,,sizeof(d));
SUM=;
for(int i=;i<=n;++i)
{
d[i]+=sumh[i]-mid;
d[s]-=sumh[i]-mid;
add(s,i,mid<<);
}
for(int i=;i<=m;++i)
{
d[t]+=suml[i]-mid;
d[n+i]-=suml[i]-mid;
add(n+i,t,mid<<);
}
for(int i=;i<=n;++i)
for(int j=;j<=m;++j)
{
d[n+j]+=L;
d[i]-=L;
add(i,n+j,R-L);
}
for(int i=;i<=t;++i)
{
if(d[i]>) add(S,i,d[i]),SUM+=d[i];
else if(d[i]<) add(i,T,-d[i]);
}
add(t,s,inf);
} bool bfs()
{
for(int i=S;i<=T;++i) lev[i]=-,cur[i]=front[i];
std::queue<int>q;
q.push(S);
lev[S]=;
int now;
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=front[now];i;i=nxt[i])
if(lev[to[i]]==- && val[i])
{
lev[to[i]]=lev[now]+;
if(to[i]==T) return true;
q.push(to[i]);
}
}
return false;
} int dinic(int now,int flow)
{
if(now==T) return flow;
int rest=,delta;
for(int &i=cur[now];i;i=nxt[i])
if(lev[to[i]]==lev[now]+ && val[i])
{
delta=dinic(to[i],std::min(flow-rest,val[i]));
if(delta)
{
val[i]-=delta;
val[i^]+=delta;
rest+=delta;
if(rest==flow) break;
}
}
if(rest!=flow) lev[now]=-;
return rest;
} int maxflow()
{
int now=;
while(bfs()) now+=dinic(S,inf);
return now;
} bool check(int mid)
{
build(mid);
return SUM==maxflow();
} int main()
{
read(n); read(m);
S=; s=n+m+; t=n+m+; T=n+m+;
int x;
for(int i=;i<=n;++i)
for(int j=;j<=m;++j)
{
read(x);
sumh[i]+=x;
suml[j]+=x;
}
read(L); read(R);
int l=,r=2e6,mid,ans=-;
while(l<=r)
{
mid=l+r>>;
if(check(mid)) ans=mid,r=mid-;
else l=mid+;
}
std::cout<<ans;
}
上一篇:3分钟看完Java 8——史上最强Java 8新特性总结之第三篇 函数式编程技巧


下一篇:bzoj千题计划143:bzoj1935: [Shoi2007]Tree 园丁的烦恼