首页 > 代码库 > Bzoj1001 [BeiJing2006]狼抓兔子

Bzoj1001 [BeiJing2006]狼抓兔子

Description

现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到,但抓兔子还是比较在行的,
而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对下面这样一个网格的地形:

 技术分享

左上角点为(1,1),右下角点为(N,M)(上图中N=4,M=5).有以下三种类型的道路 
1:(x,y)<==>(x+1,y) 
2:(x,y)<==>(x,y+1) 
3:(x,y)<==>(x+1,y+1) 
道路上的权值表示这条路上最多能够通过的兔子数,道路是无向的. 左上角和右下角为兔子的两个窝,
开始时所有的兔子都聚集在左上角(1,1)的窝里,现在它们要跑到右下解(N,M)的窝中去,狼王开始伏击
这些兔子.当然为了保险起见,如果一条道路上最多通过的兔子数为K,狼王需要安排同样数量的K只狼,
才能完全封锁这条道路,你需要帮助狼王安排一个伏击方案,使得在将兔子一网打尽的前提下,参与的
狼的数量要最小。因为狼还要去找喜羊羊麻烦.

Input

第一行为N,M.表示网格的大小,N,M均小于等于1000.
接下来分三部分
第一部分共N行,每行M-1个数,表示横向道路的权值. 
第二部分共N-1行,每行M个数,表示纵向道路的权值. 
第三部分共N-1行,每行M-1个数,表示斜向道路的权值. 
输入文件保证不超过10M

Output

输出一个整数,表示参与伏击的狼的最小数量.

Sample Input

3 4
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6

Sample Output

14
  1 #include<iostream>  2 #include<cstring>  3 #include<queue>  4 using namespace std;  5   6 struct data  7 {  8     int to,w,next;  9 }E[6000001]; 10 int n,m,node=0,ans; 11 int head[1000001],h[1000001],q[1000001]; 12  13 void insert(int u,int v,int w) 14 { 15     node++; 16     E[node].to=v; 17     E[node].w=w; 18     E[node].next=head[u]; 19     head[u]=node; 20 } 21  22 bool bfs() 23 { 24     int i; 25     memset(h,-1,sizeof(h)); 26     queue<int> Q; 27     Q.push(1); 28     h[1]=0; 29     while(!Q.empty()) 30     { 31         int p=Q.front(); 32         Q.pop(); 33         i=head[p]; 34         while(i) 35         { 36             if(E[i].w&&h[E[i].to]<0) 37             { 38                 Q.push(E[i].to); 39                 h[E[i].to]=h[p]+1; 40             } 41             i=E[i].next; 42         } 43     } 44     if(h[n*m]==-1) return 0; 45     return 1; 46 } 47  48 int dfs(int x,int f) 49 { 50     if(x==n*m) return f; 51     int i=head[x]; 52     int w,used=0; 53     while(i) 54     { 55         if(E[i].w&&h[E[i].to]==h[x]+1) 56         { 57             w=f-used; 58             w=dfs(E[i].to,min(w,E[i].w)); 59             E[i].w-=w; 60             E[i+1].w+=w; 61             used+=w; 62             if(used==f) return f; 63         } 64         i=E[i].next; 65     } 66     if(!used) h[x]=-1; 67     return used; 68 } 69  70 void dinic() 71 { 72     while(bfs()) ans+=dfs(1,0x7fffffff); 73 } 74  75 int main() 76 { 77     cin>>n>>m; 78     int x; 79     memset(head,0,sizeof(head)); 80     for(int i=1;i<=n;i++) 81         for(int j=1;j<m;j++) 82         { 83             cin>>x; 84             insert((i-1)*m+j,(i-1)*m+j+1,x); 85             insert((i-1)*m+j+1,(i-1)*m+j,x); 86         } 87     for(int i=1;i<n;i++) 88         for(int j=1;j<=m;j++) 89         { 90             cin>>x; 91             insert((i-1)*m+j,i*m+j,x); 92             insert(i*m+j,(i-1)*m+j,x); 93         } 94     for(int i=1;i<n;i++) 95         for(int j=1;j<m;j++) 96         { 97             cin>>x; 98             insert((i-1)*m+j,i*m+j+1,x); 99             insert(i*m+j+1,(i-1)*m+j,x);100         }101     dinic();102     cout<<ans;103     return 0;104 }

参考了黄学长的代码。。。所以别问我为什么这么像,看了两天的网络流。。。Orz

Bzoj1001 [BeiJing2006]狼抓兔子