2406: 矩阵 Time Limit: 10 Sec Memory Limit: 128 MB Submit: 340 Solved: 147 [Submit][Status][Discuss] Description
Input
第一行两个数n、m，表示矩阵的大小。
接下来n行，每行m列，描述矩阵A。
最后一行两个数L，R。
Output
第一行，输出最小的答案；
Sample Input
2 2
0 1
2 1
0 1
Sample Output
1
HINT
对于100%的数据满足N,M<=200,0<=L<=R<=1000,0<=Aij<=1000
Source
【分析】 二分答案+有上下界网络流
【代码】
//bzoj 2406 矩阵 #include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define inf 1e9+7 #define ll long long #define M(a) memset(a,0,sizeof a) #define fo(i,j,k) for(i=j;i<=k;i++) using namespace std; const int mxn=400005; queue <int> q; int n,m,s,t,S,T,cnt,L,R; struct edge {int to,next,flow;} f[mxn<<1]; int head[mxn],x[mxn],y[mxn],dis[mxn],du[mxn]; inline void add(int u,int v,int flow) { f[++cnt].to=v,f[cnt].next=head[u],f[cnt].flow=flow,head[u]=cnt; f[++cnt].to=u,f[cnt].next=head[v],f[cnt].flow=0,head[v]=cnt; } inline bool bfs() { memset(dis,-1,sizeof dis); q.push(S),dis[S]=0; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i;i=f[i].next) { int v=f[i].to,flow=f[i].flow; if(flow>0 && dis[v]==-1) dis[v]=dis[u]+1,q.push(v); } } return dis[T]>0; } inline int find(int u,int low) { int i,j,a,sum=0; if(u==T) return low; for(int i=head[u];i;i=f[i].next) { int v=f[i].to,flow=f[i].flow; if(flow>0 && dis[v]==dis[u]+1 && (a=find(v,min(flow,low-sum)))) { sum+=a; f[i].flow-=a; if(i&1) f[i+1].flow+=a; else f[i-1].flow+=a; if(sum==low) return sum; } } if(!sum) dis[u]=-1; return sum; } inline bool judge(int mid) { M(head),M(du);cnt=0; int i,j,tot=0,kkk=0,now=0; fo(i,1,n) fo(j,1,m) add(i,j+n,R-L),du[i]+=L,du[j+n]-=L; fo(i,1,n) add(s,i,2*mid),du[s]+=x[i]-mid,du[i]-=x[i]-mid; fo(j,1,m) add(j+n,t,2*mid),du[j+n]+=y[j]-mid,du[t]-=y[j]-mid; add(t,s,inf); fo(i,1,t) if(du[i]<0) add(S,i,-du[i]),tot-=du[i]; else if(du[i]>0) add(i,T,du[i]),kkk+=du[i]; if(kkk!=tot) return 0; while(bfs()) now+=find(S,inf); return now==kkk; } int main() { int i,j,u,v,l,r; scanf("%d%d",&n,&m); fo(i,1,n) fo(j,1,m) scanf("%d",&v),x[i]+=v,y[j]+=v; scanf("%d%d",&L,&R); s=n+m+1,t=s+1,S=s+2,T=s+3,l=0,r=2e5; while(l<r) { int mid=(l+r>>1); if(judge(mid)) r=mid; else l=mid+1; } printf("%d\n",l); return 0; }