bzoj 2406: 矩阵 （有上下界的网络流）

Description

Input

第一行两个数n、m，表示矩阵的大小。

接下来n行，每行m列，描述矩阵A。

最后一行两个数L，R。

Output

第一行，输出最小的答案；

Sample Input

Sample Output

HINT

对于100%的数据满足N,M<=200,0<=L<=R<=1000,0<=Aij<=1000

Source

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<queue>#define N 200000using namespace std;int in[N],out[N],point[N],v[N],remain[N],nxt[N];int deep[N],num[N],cur[N],ls,rs,n,m,tot;int a[203][203],sumi[N],sumj[N],last[N],ck[N];void add(int x,int y,int z){	if (!z) return;	tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; remain[tot]=z;	tot++; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; remain[tot]=0;	//cout<<x<<" "<<y<<" "<<z<<endl;}int addflow(int s,int t){	int ans=1e9; int now=t;	while (now!=s) {		ans=min(ans,remain[last[now]]);		now=v[last[now]^1];	}	now=t;	while (now!=s){		remain[last[now]]-=ans;		remain[last[now]^1]+=ans;		now=v[last[now]^1];	}	return ans;}void bfs(int s,int t){	for (int i=1;i<=t;i++) deep[i]=t;	deep[t]=0; 	queue<int> p; p.push(t);	while (!p.empty()) {		int now=p.front(); p.pop();		for (int i=point[now];i!=-1;i=nxt[i])		 if (deep[v[i]]==t&&remain[i^1])		  deep[v[i]]=deep[now]+1,p.push(v[i]);	}}void isap(int s,int t){	bfs(s,t);	int ans=0,now=s;	for (int i=1;i<=t;i++) cur[i]=point[i];	for (int i=1;i<=t;i++) num[deep[i]]++;	while (deep[s]<t) {		if (now==t) {			ans+=addflow(s,t);		    now=s;		}		bool pd=false;		for (int i=cur[now];i!=-1;i=nxt[i]) 		 if (deep[v[i]]+1==deep[now]&&remain[i]) {		 	pd=true;		 	cur[now]=i;		 	last[v[i]]=i;		 	now=v[i];		 	break;		 }		if (!pd) {			int minn=t;	    	for (int i=point[now];i!=-1;i=nxt[i]) 	    	 if (remain[i]) minn=min(minn,deep[v[i]]);	    	if (!--num[deep[now]]) break;	    	num[deep[now]=minn+1]++;	    	cur[now]=point[now];	    	if (now!=s) now=v[last[now]^1];		}	}}bool check(){	for (int i=1;i<=n+m+2;i++)	 if (remain[ck[i]^1]) return false;	return true;}bool solve(int x){	tot=-1;	memset(point,-1,sizeof(point));	memset(num,0,sizeof(num));	memset(in,0,sizeof(in));	memset(out,0,sizeof(out));	int s=1; int t=n+m+2;	for (int i=1;i<=n;i++) {		add(s,i+1,2*x);		in[i+1]+=sumi[i]-x;		out[s]+=sumi[i]-x;	}	for (int i=1;i<=m;i++) {		add(i+n+1,t,2*x);		in[t]+=sumj[i]-x;		out[i+n+1]+=sumj[i]-x;	}	for (int i=1;i<=n;i++)	 for (int j=1;j<=m;j++) {	 	add(i+1,j+n+1,rs-ls);	 	in[j+n+1]+=ls;	 	out[i+1]+=ls;	 }	int ss=t+1; int tt=ss+1;	for (int i=1;i<=t;i++){		int k=out[i]-in[i];		if (k>=0) add(i,tt,k);		else add(ss,i,-k);		ck[i]=tot;	}	add(t,s,1e9);	isap(ss,tt);	//for (int i=1;i<=n+m+1;i++)	 //cout<<remain[ck[i]^1]<<" ";	//cout<<endl;	if (check()) return true;	return false;}int main(){	freopen("a.in","r",stdin);	scanf("%d%d",&n,&m);	int sum=0;	for (int i=1;i<=n;i++)	 for (int j=1;j<=m;j++) {	  scanf("%d",&a[i][j]);	  sum+=a[i][j];	  sumi[i]+=a[i][j]; sumj[j]+=a[i][j];    }	scanf("%d%d",&ls,&rs);	int l=0; int r=sum; int ans;	//cout<<ls<<" "<<rs<<endl;	for (int i=1;i<=n;i++) r=min(r,sumi[i]);	for (int i=1;i<=m;i++) r=min(r,sumj[i]);	ans=r;	//cout<<l<<" "<<r<<endl;	while (l<=r) {		int mid=(l+r)/2;		if (solve(mid)) ans=min(ans,mid),r=mid-1;		else l=mid+1; 	}	PRintf("%d/n",ans);}