这题……建模部分先略过
这道题是会卡时限的T_T俺的Dinic被卡了，在此放几篇很棒的讲网络流算法的文章，至于大家耳熟能详的论文就不放了……
http://www.cppblog.com/panzhizhou/articles/172978.html?opt=admin 里面的各种超链接也很不错的……好的来重新更新一下……这题因为要二分，需要多次重建跑最大流，所以不能用像lrj大爷的白书上那样用vector存边（太慢），需用前向星= =
然后……本蒻由于第一次写前向星，且印象中好像不加【当前弧优化】效率也不会低太多……所以顺利TLE了。事实上当前弧的设计还是和vector存边时差不多的，而且很有必要优化这一下……
round #1 2b版：
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_JUDGE 168 freopen("input.txt","r",stdin); 169 // freopen("output.txt","w",stdout); 170 #endif 171 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 }
round #2 修改（缩短）版：
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_JUDGE 145 freopen("input.txt","r",stdin); 146 #endif 147 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 }
原文：http://www.cnblogs.com/Tunix/p/4216319.html
