输出一个整数，表示参与伏击的狼的最小数量.
2015.4.16新加数据一组，可能会卡掉从前可以过的程序。
这不就是最小割模型么...但是数据范围23333...然而居然跑过了...
还是看正解吧...平面图转对偶图...
我们从s到t连一条边增加一个区域S，无穷大的区域为T...然后有相邻边的区域连一条权值为边权值的边，ST不连边，此时S到T的最短路就是st的最小割...
1 #include<algorithm> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 #include<queue> 6 //by NeighThorn 7 #define inf 0x3f3f3f3f 8 using namespace std; 9 10 const int maxn=2000000+5,maxm=10000000+5; 11 12 int n,m,S,T,ans,cnt,w[maxm],hd[maxn],to[maxm],nxt[maxm],vis[maxn],dis[maxn]; 13 14 inline int spfa(void){ 15 memset(dis,inf,sizeof(dis)); 16 queue<int> q;q.push(S),vis[S]=1,dis[S]=0; 17 while(!q.empty()){ 18 int top=q.front();q.pop();vis[top]=0; 19 for(int i=hd[top];i!=-1;i=nxt[i]) 20 if(dis[to[i]]>dis[top]+w[i]){ 21 dis[to[i]]=dis[top]+w[i]; 22 if(!vis[to[i]]) 23 vis[to[i]]=1,q.push(to[i]); 24 } 25 } 26 return dis[T]; 27 } 28 29 inline void add(int s,int x,int y){ 30 w[cnt]=s;to[cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt++; 31 w[cnt]=s;to[cnt]=x;nxt[cnt]=hd[y];hd[y]=cnt++; 32 } 33 34 signed main(void){ 35 // freopen("in.txt","r",stdin); 36 memset(hd,-1,sizeof(hd)); 37 scanf("%d%d",&n,&m);S=0,T=(n-1)*(m-1)*2+1; 38 if(n==1){ans=inf; 39 for(int i=1,x;i<m;i++) 40 scanf("%d",&x),ans=min(ans,x); 41 printf("%d\n",ans);return 0; 42 } 43 else if(m==1){ans=inf; 44 for(int i=1,x;i<n;i++) 45 scanf("%d",&x),ans=min(ans,x); 46 printf("%d\n",ans);return 0; 47 } 48 for(int i=1;i<=n;i++) 49 for(int j=1,x;j<m;j++){ 50 scanf("%d",&x); 51 if(i==1) 52 add(x,(j-1)*2+1,T); 53 else if(i==n) 54 add(x,(i-2)*(m-1)*2+j*2,S); 55 else 56 add(x,(i-2)*(m-1)*2+j*2,(i-1)*(m-1)*2+(j-1)*2+1); 57 } 58 for(int i=1;i<n;i++) 59 for(int j=1,x;j<=m;j++){ 60 scanf("%d",&x); 61 if(j==1) 62 add(x,S,(i-1)*(m-1)*2+2); 63 else if(j==m) 64 add(x,T,i*(m-1)*2-1); 65 else 66 add(x,(i-1)*(m-1)*2+(j-2)*2+1,(i-1)*(m-1)*2+j*2); 67 } 68 for(int i=1;i<n;i++) 69 for(int j=1,x;j<m;j++) 70 scanf("%d",&x),add(x,(i-1)*(m-1)*2+(j-1)*2+1,(i-1)*(m-1)*2+(j-1)*2+2); 71 printf("%d\n",spfa()); 72 return 0; 73 }
By NeighThorn
原文：http://www.cnblogs.com/neighthorn/p/6256669.html
