首页 > 代码库 > BZOJ 2406 二分+有上下界的网络流判定
BZOJ 2406 二分+有上下界的网络流判定
思路:
求出每行的和 sum_row
每列的和 sum_line
二分最后的答案mid
S->i 流量[sum_row[i]-mid,sum_row[i]+mid]
i->n+j 流量[L,R]
n+j->T 流量 [sum_line[i]-mid,sum_line[i]+mid]
套用有上下界的网络流 判一下就好了..
这是道有上下界网络流的裸题
//By SiriusRen#include <queue>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N=205,M=222222;int n,m,a[N][N],sum_row[N],sum_line[N],L,R;struct Dinic{ int first[N*2],next[M],v[M],w[M],vis[N*2],tot,T,SS,TT,jy,du[N*2],all; void Add(int x,int y,int z){w[tot]=z,v[tot]=y,next[tot]=first[x],first[x]=tot++;} void add(int x,int y,int z){Add(x,y,z),Add(y,x,0);} bool tell(){ memset(vis,-1,sizeof(vis)),vis[SS]=0; queue<int>q;q.push(SS); while(!q.empty()){ int t=q.front();q.pop(); for(int i=first[t];~i;i=next[i]) if(vis[v[i]]==-1&&w[i]) vis[v[i]]=vis[t]+1,q.push(v[i]); }return vis[TT]!=-1; } int zeng(int x,int y){ if(x==TT)return y; int r=0; for(int i=first[x];~i&&y>r;i=next[i]) if(vis[v[i]]==vis[x]+1&&w[i]){ int t=zeng(v[i],min(y-r,w[i])); w[i]-=t,w[i^1]+=t,r+=t; } if(!r)vis[x]=-1; return r; } int flow(){ int ans=0; while(tell())while(jy=zeng(SS,0x3f3f3f3f))ans+=jy; return ans; } bool check(int x){ memset(first,-1,sizeof(first)), all=tot=0,T=n+m+1,SS=n+m+2,TT=n+m+3, memset(du,0,sizeof(du)); add(T,0,0x3f3f3f3f); for(int i=1;i<=n;i++)add(0,i,2*x),du[i]+=sum_row[i]-x,du[0]-=sum_row[i]-x; for(int i=1;i<=m;i++)add(i+n,T,2*x),du[T]+=sum_line[i]-x,du[i+n]-=sum_line[i]-x; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) add(i,j+n,R-L),du[j+n]+=L,du[i]-=L; for(int i=0;i<=T;i++){ if(du[i]>0)add(SS,i,du[i]),all+=du[i]; else add(i,TT,-du[i]); }if(flow()>=all)return 1; return 0; }}d;int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ scanf("%d",&a[i][j]); sum_row[i]+=a[i][j]; sum_line[j]+=a[i][j]; } scanf("%d%d",&L,&R); int l=0,r=200000,ans=0; while(l<=r){ int mid=(l+r)>>1; if(d.check(mid))r=mid-1,ans=mid; else l=mid+1; }printf("%d\n",ans);}
BZOJ 2406 二分+有上下界的网络流判定
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。