[例题]最小矩阵差——有上下界的网络流问题
题目描述：
给定一个n*m(n.m<=200)的矩阵A，最小化：
Max{
max {|∑(A ij ? B ij )|} 1≤j≤ m
max {|∑(A ij ? B ij ) |} 1≤i≤n
<1>题目分析
这题的形式十分像线性规划问题，因此可以考虑用网络流。
网络流处理矩阵类问题的一种经典做法是——开一排表示行的节点，开一排表示列的节点，然后balabala……
于是这题的模型大概就出来了……
<2>有上下界网络流问题的模型构建
基本思想是考虑自由流，即除去满足下界的流。
先考虑无源无汇的情况：
新建源S汇T。对于每个节点d，设其入弧下界和为in，出弧下界和为out：
1.若in>out则连S->d，容量为delta。
2.若in<out则连d->T，容量为delta。
3.将每条原弧容量改成上界减下界。
从S到T跑一遍最大流，如果每条和S或T相连的边均满流，则有可行流，否则不存在可行流。
如果有源有汇呢……？直接从汇到源连一条容量为无穷的边就行了。
<3>算法描述
二分枚举答案ans，那么对每一行每一列的总和就有要求的最小和最大值了。
于是流量表示数值，稍微YY下图就构出来了。
注意区分原来的s t和新建的S T……
Code：
#include<cstdio>#include<cstring>using namespace std;const int SN=500, SM=100010, oo=999999999;#define max(_,__) ({ int ___=_,____=__; (___>____)?___:____; })#define min(_,__) ({ int ___=_,____=__; (___<____)?___:____; })int n,m,A[300][300],ht[300],lt[300],B[300][300];int lans,rans,md,L,R,s,t,S,T;int tot[SN],la[SN],fr[SM],to[SM],rs[SM],nx[SM],bn;int ln[SN],l,r,hei[SN],Bt,vis[SN];void link(int u, int v, int w){ bn++, fr[bn]=u, to[bn]=v, rs[bn]=w, nx[bn]=la[u], la[u]=bn; bn++, fr[bn]=v, to[bn]=u, rs[bn]=0, nx[bn]=la[v], la[v]=bn;}void clean(){ Bt=0, bn=1; memset(tot,0,sizeof(tot)); memset(vis,0,sizeof(vis)); memset(la ,0,sizeof(la ));}bool BFS(){ int j; for(ln[l=r=1]=T,hei[T]=1,vis[T]=++Bt; l<=r; l++) for(j=la[ln[l]]; j; j=nx[j]) if(rs[j^1] && vis[to[j]]!=Bt) { ln[++r]=to[j], vis[to[j]]=Bt; hei[to[j]]=hei[ln[l]]+1; if(to[j]==S) return true; } return false;}int DFS(int d, int p){ int j,flow=0,f; if(d==T || p==0) return p; for(j=la[d]; j; j=nx[j]) if(vis[to[j]]==Bt && hei[to[j]]==hei[d]-1) if( rs[j] && ( f=DFS(to[j], min(p,rs[j])) )>0 ) { rs[j]-=f, rs[j^1]+=f; flow+=f, p-=f; if(!p) return flow; } hei[d]=oo; return flow;}bool canflow(){ while(BFS()) DFS(S,oo); for(int j=2; j<=bn; j++) if( (fr[j]==S || to[j]==T) && j<(j^1) && rs[j] ) return false; return true;}bool solve(){ int i,j,dw,up; clean(); s=n+m+1,t=s+1; S=t+1,T=S+1; for(i=1; i<=n; i++) dw=max(ht[i]-md,0), up=ht[i]+md, tot[ i ]+=dw, link( s , i, up-dw), tot[s]-=dw; for(i=1; i<=m; i++) dw=max(lt[i]-md,0), up=lt[i]+md, tot[i+n]-=dw, link(i+n, t, up-dw), tot[t]+=dw; for(i=1; i<=n; i++) for(j=1; j<=m; j++) tot[i]-=L, tot[j+n]+=L, link(i, j+n, R-L); link(t, s, oo); for(i=1; i<=t; i++) { if(tot[i]>0) link(S, i, tot[i]); if(tot[i]<0) link(i, T, -tot[i]); } return canflow();}int main(){ int i,j; freopen("mat.in" , "r", stdin); freopen("mat.out", "w", stdout); scanf("%d%d", &n, &m); for(i=1; i<=n; i++) for(j=1; j<=m; j++) { scanf("%d", &A[i][j]); ht[i] += A[i][j]; lt[j] += A[i][j]; } scanf("%d%d", &L, &R); for(lans=0,rans=200000,md=(lans+rans)/2; lans<rans; md=(lans+rans)/2) if(solve()) rans=md; else lans=md+1; md=lans; solve(); printf("%d\n", md); for(i=2; i<=bn; i++) if(fr[i]>=1 && fr[i]<=n && i<(i^1)) B[fr[i]][to[i]-n] = R-rs[i]; for(i=1; i<=n; i++) { for(j=1; j<=m; j++) printf("%d ", B[i][j]); printf("\n"); } return 0;}