BZOJ 1001, 狼抓兔子

Problem

传送门

Mean

求平面图最小割。

Analysis

数据范围太大导致直接跑最大流会TLE（然而据说只要姿势不太丑都能水过去）。 正确做法是平面图转对偶图，就可以把最小割问题转化成求最短路（Orz，太神了……）。 注意要特判 n=1 与 m=1 的情况。

参考资料：周冬2008年集训队论文《两极相通——浅析最大—最小定理在信息学竞赛中的应用》

Code

#include<cstdio> const int N=1005,INF=~0U>>2; int n,m,e,ed,cur,x,h=1,t,i,j,ans=INF,r[N][N],c[N][N],d[N][N],v[N*N*6],f[N*N*6],nxt[N*N*6],g[N*N*2],dis[N*N*2],q[N*N*2]; bool in[N*N*2]; void addedge(int x,int y,int w){ v[++ed]=y,f[ed]=w; nxt[ed]=g[x]; g[x]=ed; } void add(int x,int w){ if(w>dis[x]) return; dis[x]=w; if(!in[x]){ in[x]=1; if(w<dis[q[h]]){ if(--h<1) h+=e; q[h]=x; }else{ if(++t>e) t-=e; q[t]=x; } } } int main(){ scanf("%d%d",&n,&m); for(i=1;i<=n;i++) for(j=1;j<m;j++) scanf("%d",&r[i][j]); for(i=1;i<n;i++) for(j=1;j<=m;j++) scanf("%d",&c[i][j]); for(i=1;i<n;i++) for(j=1;j<m;j++) scanf("%d",&d[i][j]); if(n==1 && m==1){printf("0");return 0;} if(n==1){ for(int i=1;i<m;i++) if(r[1][i]<ans) ans=r[1][i]; printf("%d",ans); return 0; } if(m==1){ for(int i=1;i<n;i++) if(c[i][1]<ans) ans=c[i][1]; printf("%d",ans); return 0; } e=(n-1)*(m-1)*2+1; for(i=1;i<n;i++) for(j=1;j<m;j++){ cur=(i-1)*(m-1)*2+j; if(i==1) addedge(cur,e,r[i][j]),addedge(e,cur,r[i][j]); if(i==n-1) addedge(cur+m-1,0,r[i+1][j]),addedge(0,cur+m-1,r[i+1][j]); if(j==1) addedge(cur+m-1,0,c[i][j]),addedge(0,cur+m-1,c[i][j]); if(j==m-1) addedge(cur,e,c[i][j+1]),addedge(e,cur,c[i][j+1]); if(i!=n-1) addedge(cur+(m-1)*2,cur+m-1,r[i+1][j]),addedge(cur+m-1,cur+(m-1)*2,r[i+1][j]); if(j!=m-1) addedge(cur,cur+m,c[i][j+1]),addedge(cur+m,cur,c[i][j+1]); addedge(cur,cur+m-1,d[i][j]),addedge(cur+m-1,cur,d[i][j]); } for(i=0;i<=e;i++) dis[i]=INF; add(0,0); while(h!=t+1){ int tmp=h; if(++h>e) h-=e; for(i=g[x=q[tmp]],in[x]=0;i;i=nxt[i]) add(v[i],dis[x]+f[i]); } printf("%d",dis[e]); return 0; }