View Code #include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #define min(a,b) (a)>(b)?(b):(a) #define max(a,b) (a)>(b)?(a):(b) #define inf 99999999 using namespace std; int cnt; int source,N; int sink,ans; int c[54400]; int H[520410]; int d[54410]; struct egde { int u,v,c,next; }; egde a[520000]; void init() { int i; for(i=0;i<520000;i++) H[i]=-1; cnt=0; } void add(int u,int v,int c) { a[cnt].v=v; a[cnt].c=c; a[cnt].next=H[u]; H[u]=cnt++; } void build(int u,int v,int c) { add(u,v,c); add(v,u,0); } int dfs(int u,int flow) { if(u==sink) return flow; int tt,res=0,delta; for(tt=H[u];~tt;tt=a[tt].next) { int &v=a[tt].v,&c=a[tt].c; if(c&&d[u]==d[v]+1){ delta=dfs(v,min(flow,c)); c-=delta; a[tt^1].c+=delta; res+=delta; flow-=delta; if (!flow) return res; } } if(!res) { if(!--c[d[u]]) d[source]=N+3; ++c[++d[u]]; } return res; } void sap() { memset(c,0,sizeof(c)); memset(d,0,sizeof(d)); c[source]=N; while(d[source]<N) ans+=dfs(source,inf); } int main() { int n,m,x,i,j; int cases=1; while(~scanf("%d%d",&n,&m)) { init(); ans=0; source = 0; sink=n*m+1; N=sink+1; for(i=1;i<=n;++i) for(j=1;j<=m;++j) { scanf("%d",&x); if(i>1)//上 build((i-1)*m+j,(i-2)*m+j,1); if(i<n)//下 build((i-1)*m+j,i*m+j,1); if(j>1)// left build((i-1)*m+j,(i-1)*m+j-1,1); if(j<m)// right build((i-1)*m+j,(i-1)*m+j+1,1); if(x==1) build((i-1)*m+j,sink,inf); else if(x==2) build(source,(i-1)*m+j,inf); } sap(); printf("Case %d:\n%d\n",cases++,ans); } return 0; }
转载于:https://www.cnblogs.com/ray007great/archive/2013/05/08/3066085.html
相关资源：数据结构—成绩单生成器