网络流-最大流

  1 /**************************************************************  2     Problem: 2756  3     User: ProgrammingApe  4     Language: C++  5     Result: Accepted  6     Time:8000 ms  7     Memory:2008 kb  8 ****************************************************************/  9   10 //BZOJ 2756 11 #include<queue> 12 #include<cstdio> 13 #include<vector> 14 #include<cstring> 15 #include<cstdlib> 16 #include<iostream> 17 #include<algorithm> 18 #define rep(i,n) for(int i=0;i<n;++i) 19 #define F(i,j,n) for(int i=j;i<=n;++i) 20 #define D(i,j,n) for(int i=j;i>=n;--i) 21 #define pb push_back 22 using namespace std; 23 const int N=50,INF=~0u>>2; 24 const long long infll=~0uLL>>2; 25 const int fx[]={1,0,-1,0}, 26           fy[]={0,1,0,-1}; 27 typedef long long LL; 28 //#define debug 29   30 void read(int &v){ 31     v=0; int sig=1; 32     char ch=getchar(); 33     while(ch<‘0‘||ch>‘9‘){ if (ch==‘-‘) sig=-1; ch=getchar();} 34     while(ch>=‘0‘&&ch<=‘9‘){ v=v*10+ch-‘0‘; ch=getchar();} 35     v*=sig; 36 } 37   38 int n,m,a[N][N],d[N*N],cur[N*N],s,t,cnt; 39 bool color[N][N]; 40 LL sum[2]; 41 struct edge{ 42     int from,to; 43     LL cap,flow; 44     int next; 45 }E[N*N*10]; 46 int head[2000]; 47 //vector<edge>E; 48 //vector<int>G[2000]; 49   50 void add(int from,int to,LL cap){ 51     E[++cnt]=(edge){from,to,cap,0,head[from]}; 52     head[from]=cnt; 53     E[++cnt]=(edge){to,from,0,0,head[to]}; 54     head[to]=cnt; 55 } 56 //queue<int>Q;//·ÅÔÚmklevelÀïÃæ»áÂýÐí¶à 57 int Q[N*N]; 58 bool mklevel(){ 59     memset(d,63,sizeof d); 60     int l=0,r=0; 61     d[s]=0; Q[r++]=s; 62     while(l<r){ 63         int x=Q[l++]; 64         for(int i=head[x];i;i=E[i].next){ 65             edge&e=E[i]; 66             if (d[e.to]>200000 && e.cap>e.flow){ 67                 d[e.to]=d[x]+1; 68                 Q[r++]=e.to; 69             } 70         } 71     } 72     return d[t]<200000; 73 } 74 LL dfs(int x,LL a){ 75     if (x==t||a==0) return a; 76     LL flow=0; 77     for(int &i=cur[x];i;i=E[i].next){ 78         edge&e=E[i]; 79         if (d[e.to]!=d[x]+1) continue; 80         LL f=dfs(e.to,min(a,e.cap-e.flow)); 81         if (f>0){ 82             flow+=f; 83             e.flow+=f; 84             E[((i-1)^1)+1].flow-=f; 85             a-=f; 86             if (a==0) break; 87         } 88     } 89     return flow; 90 } 91 LL dinic(){ 92     LL flow=0; 93     while(mklevel()){ 94         F(i,s,t) cur[i]=head[i];//µ±Ç°»¡ÓÅ»¯ºÜÖØÒªµÄT_T 95         flow+=dfs(s,infll);//ÕâÀïÒ²Òª¸Ä³Éinfll 96     } 97     return flow; 98 } 99 LL Total=0;100 int maxw=0;101 void solve1(){102     memset(E,0,sizeof E);103     memset(head,0,sizeof head); cnt=0;104     LL d=sum[0]-sum[1];105     if (d<maxw) {printf("-1\n"); return;}106     int x,y;107     Total=0;108     F(i,1,n)109         F(j,1,m){110 //          if (a[i][j]>d) {printf("-1\n"); return;}111             if (color[i][j]) add((i-1)*m+j,t,d-a[i][j]);112             else{113                 add(s,(i-1)*m+j,d-a[i][j]);114                 F(k,0,3){115                     x=i+fx[k],y=j+fy[k];116                     if (x<1||y<1||x>n||y>m) continue;117                     add( (i-1)*m+j , (x-1)*m+y , infll);118                 }119                 Total+=d-a[i][j];120             }121         }122     LL ans=dinic();123     if (Total==ans) printf("%lld\n",ans);124     else printf("-1\n");125 }126  127 bool check(LL x){128     memset(E,0,sizeof E);129     memset(head,0,sizeof head);130     cnt=0;//Çå¿Õ±ß¼¯Êý×éµÄʱºò£¬¼ÇµÃ°Ñ±ß¼¯´óСcntÒ²Çå¿Õ131     Total=0;132     F(i,1,n)133         F(j,1,m){134             if (color[i][j]) add( (i-1)*m+j,t,x-a[i][j] );135             else{136                 add(s,(i-1)*m+j,x-a[i][j]);137                 F(k,0,3){138                     int tx=i+fx[k],ty=j+fy[k];139                     if (tx<1||ty<1||tx>n||ty>m) continue;140                     add( (i-1)*m+j , (tx-1)*m+ty , infll);141                 }142                 Total+=x-a[i][j];143             }144         }145     LL flow=dinic();146     return Total==flow;147 }148  149 void solve(){//Èç¹ûÊÇżÊý£º¶þ·Ö150     if (sum[0]!=sum[1]){151         printf("-1\n");152         return;153     }154     LL l=maxw,r=l*2,mid,ans=-1;//¾ÓÈ»ÊÇÕâÀïÍüÁ˸ġ­155     while(l<r){156 //      cout <<l<<" "<<r<<endl;157 //      printf("l=%lld r=%lld\n",l,r);158         mid=l+r>>1;159         if (check(mid)) {ans=Total; r=mid;}160         else l=mid+1;161     }162     if (ans!=-1) printf("%lld\n",ans);163     else printf("-1\n");164 }165  166 int main(){167     #ifndef ONLINE_JUDGE168     freopen("input.txt","r",stdin);169 //  freopen("output.txt","w",stdout);170     #endif171     int T;172     scanf("%d",&T);173     while(T--){174         read(n),read(m);175         s=0; t=n*m+1;176         memset(a,0,sizeof a);177         memset(color,0,sizeof color);178         sum[0]=sum[1]=maxw=0;179         F(i,1,n) F(j,1,m) {180             read(a[i][j]);181             color[i][j]=(i+j)&1;182             sum[color[i][j]]+=a[i][j];183             maxw=max(maxw,a[i][j]);184         }185         if ((n&1) && (m&1)) solve1();186         else solve();187     }188     return 0;189 }

  1 /**************************************************************  2     Problem: 2756  3     User: Tunix  4     Language: C++  5     Result: Accepted  6     Time:7912 ms  7     Memory:1552 kb  8 ****************************************************************/  9   10 //BZOJ 2756 11 #include<cstdio> 12 #include<cstring> 13 #include<cstdlib> 14 #include<algorithm> 15 #define rep(i,n) for(int i=0;i<n;++i) 16 #define F(i,j,n) for(int i=j;i<=n;++i) 17 #define D(i,j,n) for(int i=j;i>=n;--i) 18 using namespace std; 19 typedef long long LL; 20 //#define debug 21 const int N=50; 22 const long long infll=~0uLL>>2; 23 const int fx[]={0,1,-1,0}, 24           fy[]={1,0,0,-1}; 25   26 void read(int &v){ 27     int sign=1; v=0; 28     char ch=getchar(); 29     while(ch<‘0‘ || ch>‘9‘){ if(ch==‘-‘) sign=-1; ch=getchar();} 30     while(ch>=‘0‘ && ch<=‘9‘) {v=v*10+ch-‘0‘; ch=getchar();} 31     v*=sign; 32 } 33 /*********************网络流**********************/ 34 int n,m,val[N][N],color[N][N],cnt=0,s,t; 35 int head[N*N],cur[N*N]; 36 LL sum[2]; 37 struct edge{ 38     int from,to; 39     LL cap,flow; 40     int next; 41 }E[N*N*10]; 42   43 void add(int from,int to,LL cap){ 44     E[++cnt]=(edge){from,to,cap,0,head[from]}; 45     head[from]=cnt; 46     E[++cnt]=(edge){to,from,0,0,head[to]}; 47     head[to]=cnt; 48 } 49   50 int d[N*N],Q[N*N]; 51 bool mklevel(){ 52     memset(d,63,sizeof d); 53     d[s]=0; int l=0,r=0; 54     Q[r++]=s; 55     while(l<r){ 56         int x=Q[l++]; 57         for(int i=head[x];i;i=E[i].next){ 58             edge &e=E[i]; 59             if (d[e.to]>200000 && e.cap>e.flow){ 60                 d[e.to]=d[x]+1; 61                 Q[r++]=e.to; 62             } 63         } 64     } 65     return d[t]<200000; 66 } 67 LL dfs(int x,LL a){ 68     if (x==t || a==0) return a; 69     LL flow=0,f; 70     for(int &i=cur[x];i;i=E[i].next){ 71         edge &e=E[i]; 72         if (d[e.to]!=d[x]+1) continue; 73         f=dfs(e.to,min(a,e.cap-e.flow)); 74         if (f>0){ 75             e.flow+=f; 76             flow+=f; 77             a-=f; 78             E[((i-1)^1)+1].flow-=f; 79             if (a==0) break; 80         } 81     } 82     return flow; 83 } 84 LL dinic(){ 85     LL flow=0; 86     while(mklevel()) { 87         F(i,s,t) cur[i]=head[i]; 88         flow+=dfs(s,infll); 89     } 90     return flow; 91 } 92 /*************************************************/ 93 inline int get(int x,int y){ return (x-1)*m+y; } 94 LL total; 95 inline bool check(LL D){ 96     memset(E,0,sizeof E); 97     memset(head,0,sizeof head); 98     cnt=0; total=0; 99     F(i,1,n)100         F(j,1,m){101             if (color[i][j]) add( get(i,j),t,D-val[i][j] );102             else{103                 add( s,get(i,j),D-val[i][j] );104                 F(k,0,3){105                     int tx=i+fx[k],ty=j+fy[k];106                     if (tx<1||ty<1||tx>n||ty>m) continue;107                     add( get(i,j),get(tx,ty),infll );108                 }109                 total+=D-val[i][j];110             }111         }112     LL flow=dinic();113     return total==flow;114 }115  116 int maxw;117 void work(){118     s=0; t=n*m+1;119     if ((n&1) && (m&1)){120         LL D=sum[0]-sum[1];121         if (D<maxw) printf("-1\n");122         else{123             if(check(D)) printf("%lld\n",total);124             else printf("-1\n");125         }126     }127     else {128         if (sum[0]!=sum[1]){129             printf("-1\n");130             return;131         }132         LL l=maxw,r=l*2,mid,ans=-1;133         while(l<r){134 //          printf("l=%lld r=%lld\n",l,r);135             mid=l+r>>1;136             if (check(mid)) {r=mid; ans=total;}137             else l=mid+1;138         }139         if (ans==-1) printf("-1\n");140         else printf("%lld\n",ans);141     }142 }143 int main(){144     #ifndef ONLINE_JUDGE145     freopen("input.txt","r",stdin);146     #endif147     int T; read(T);148     while(T--){149         memset(val,0,sizeof val);150         memset(color,0,sizeof color);151         sum[0]=sum[1]=0;152         maxw=0;153         read(n); read(m);154         F(i,1,n)155             F(j,1,m){156                 read(val[i][j]);157                 color[i][j]=(i+j)&1;158                 sum[color[i][j]]+=val[i][j];159                 if (val[i][j]>maxw) maxw=val[i][j];160             }161         work();162     }163     return 0;164 }