输出一个整数，表示参与伏击的狼的最小数量.
2015.4.16新加数据一组，可能会卡掉从前可以过的程序。
最大流最小割定理
#include<queue> #include<cstdio> #include<string> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define F(i,l,r) for(int i=l;i<r;i++) #define N 1000001 #define inf 1e9+5 inline int read() { int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } struct ljn{int fro,to,v;}e[N*6]; int cnt=1,lj[N],n,m,tt,ans=0,S,T,dis[N]; inline void add(int u,int v,int p){cnt++;e[cnt].to=v;e[cnt].fro=lj[u];e[cnt].v=p;lj[u]=cnt;} inline bool bfs() { F(i,S,T+1) dis[i]=0; dis[S]=1; static queue<int>q; q.push(S); while(!q.empty()) { int tp=q.front(); q.pop(); for(int i=lj[tp];i;i=e[i].fro) { if(e[i].v&&!dis[e[i].to]) { dis[e[i].to]=dis[tp]+1; q.push(e[i].to); } } } return dis[T]?1:0; } inline int dfs(int x,int p) { if(x==T||p==0) return p; int tmp=0,tp; for(int i=lj[x];i;i=e[i].fro) { if(e[i].v&&dis[e[i].to]==dis[x]+1) { tp=dfs(e[i].to,min(p-tmp,e[i].v)); e[i].v-=tp; e[i^1].v+=tp; tmp+=tp; if(p==tmp) return tmp; } } if(tmp==0) dis[x]=0; return tmp; } int main() { n=read();m=read(); S=0;T=n*m+1; add(S,1,inf);add(1,S,inf); add(m*n,T,inf);add(T,m*n,inf); F(i,0,n) F(j,1,m) { tt=read(); add(i*m+j,i*m+j+1,tt); add(i*m+j+1,i*m+j,tt); } F(i,0,n-1) F(j,1,m+1) { tt=read(); add(i*m+j,(i+1)*m+j,tt); add((i+1)*m+j,i*m+j,tt); } F(i,0,n-1) F(j,1,m) { tt=read(); add(i*m+j,(i+1)*m+j+1,tt); add((i+1)*m+j+1,i*m+j,tt); } while(bfs()) ans+=dfs(S,inf); printf("%d\n",ans); }
原文：http://www.cnblogs.com/lkhll/p/6268689.html