【二分+上下界网络流】BZOJ2406 矩阵

网络安全


题面在这里

好题，好题啊！！

此题乍一看好像和网络流完全没有关联
其实暗藏玄机

题面不讲人话……
其实就是使矩阵A-B的每一行每一列的绝对值的最大值最小

显然可以看出要二分
枚举一个当前的最大值M，则下式恒成立：


|SAi−SBi|≤M
等价于下式:


SAi−M≤SBi≤SAi+M
（有同学可能不能理解，建议从绝对值的几何意义考虑）

然后把每个B矩阵中的数字看作流量
每一行、每一列看作一个点
因为

SAi−M≤SBi≤SAi+M
所以

S→i[SAi−M,SAi+M]
（[]内表示流量范围）
同理

S→j[SAj−M,SAj+M]

又有每个点的取值为[L,R]
即单个行与列之间的流量联系在[L,R]内


i→j[L,R]
然后就套用“有源汇上下界可行流”

示例程序：

#include
#include
#include
using namespace std;
const int maxn=405,maxe=200005,INF=0x3f3f3f3f;
int n,m,s_i[maxn],s_j[maxn],l,r,S,T,SS,TT;
int tot,lnk[maxn],son[maxe],nxt[maxe],cap[maxe],flw[maxe];
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int red(){
    int res=0,f=1;char ch=nc();
    while (ch<'0'||'9'if (ch=='-') f=-f;ch=nc();}
    while ('0'<=ch&&ch<='9') res=res*10+ch-48,ch=nc();
    return res*f;
}
inline void add(int x,int y,int z){
    son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;cap[tot]=z;flw[tot]=0;
    son[++tot]=x;nxt[tot]=lnk[y];lnk[y]=tot;cap[tot]=0;flw[tot]=0;
}
int d[maxn],pos[maxn],que[maxn],tmp[maxn];
bool bfs(int S,int T){
    memset(d,63,sizeof(d));
    int hed=0,til=1;
    que[1]=S;d[S]=0;
    while (hed!=til)
     for (int j=lnk[que[++hed]];j;j=nxt[j])
      if (d[son[j]]==INF&&flw[j]1;
    return d[T]!=INF;
}
int dfs(int x,int flow,int T){
    if (x==T||flow==0) return flow;
    int res=0,f;
    for (int &j=pos[x];j;j=nxt[j])
     if (d[son[j]]==d[x]+1&&(f=dfs(son[j],min(flow,cap[j]-flw[j]),T))>0){
        flw[j]+=f;flw[j^1]-=f;
        res+=f;flow-=f;
        if (flow==0) break;
     }
    return res;
}
int Dinic(int S,int T){
    int res=0;
    while (bfs(S,T)){
        memcpy(pos,lnk,sizeof(lnk));
        res+=dfs(S,INF,T);
    }
    return res;
}
bool check(int mid){
    memset(lnk,0,sizeof(lnk));
    memset(tmp,0,sizeof(tmp));
    tot=1;
    int N=n+m;S=N+1;T=N+2;SS=N+3;TT=N+4;
    for (int i=1;i<=n;i++){
        int L=max(0,s_i[i]-mid),R=s_i[i]+mid;
        add(S,i,R-L);tmp[S]-=L;tmp[i]+=L;
    }
    for (int j=1;j<=m;j++){
        int L=max(0,s_j[j]-mid),R=s_j[j]+mid;
        add(j+n,T,R-L);tmp[j+n]-=L;tmp[T]+=L;
    }
    for (int i=1;i<=n;i++)
     for (int j=1;j<=m;j++)
      add(i,j+n,r-l),tmp[i]-=l,tmp[j+n]+=l;
    int blc=0;
    for (int i=1;i<=N+2;i++)
     if (tmp[i]>0) add(SS,i,tmp[i]),blc+=tmp[i];else add(i,TT,-tmp[i]);
    add(T,S,INF);
    return blc==Dinic(SS,TT);
}
int main(){
    n=red(),m=red();
    for (int i=1;i<=n;i++)
     for (int j=1,x;j<=m;j++)
      x=red(),s_i[i]+=x,s_j[j]+=x;
    l=red(),r=red();
    int L=0,R=2e5,ans;
    while (L<=R){
        int mid=L+R>>1;
        if (check(mid)) R=mid-1,ans=mid;else L=mid+1;
    }
    printf("%d",ans);
    return 0;
}