1001: [BeiJing2006]The wolf grabbed the rabbit
Time Limit: 15 Sec Memory Limit: 162 MB
Submit: 28885 Solved: 7540
[Submit][Status][Discuss]
Description
Now the children’s favorite “Pleasant Goat and Grey Wolf” is that Grey Wolf can’t catch sheep, but it’s better to catch rabbits.
And now the rabbits are stupid. They have only two nests. Now, as the wolf king, you face a grid of terrain below.
The upper left corner is (1,1), and the lower right corner is (N, M) (N=4, M=5 above). There are three types of roads.
1:(x,y)<==>(x+1,y)
2:(x,y)<==>(x,y+1)
3:(x,y)<==>(x+1,y+1)
The weight on the road indicates the maximum number of rabbits that can be passed along the road. The road is undirected. The upper left corner and the lower right corner are the two nests of rabbits.
At first all the rabbits gathered in the upper left corner (1,1) of the nest, and now they’re running to the lower right (N,M) of the nest, and Wolf King ambushes.
These rabbits, of course, for the sake of safety, if the maximum number of rabbits on a road is K, the wolf king needs to arrange the same number of K wolves.
To completely block the road, you need to help the Wolf King arrange an ambush plan so that the rabbit can be caught and participated.
The number of wolves is the smallest. Because wolves have trouble finding happy sheep.
Input
The first behavior N, M. indicates the size of the grid, N and M are all less than or equal to 1000..
Then there are three parts.
The first part contains N rows, M-1 numbers per row to indicate the weight of the cross road.
The second part of the N-1 row, each row M number, indicating the weight of the longitudinal road.
The third part of the N-1 row, each row M-1 number, indicating the weight of the oblique road.
The input file is guaranteed to be no more than 10M
Output
Output an integer indicating the minimum number of wolves participating in ambush.
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
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
It is easy to see that this is a problem of finding minimal cuts, but the graph is too large for network flow to run. Some people on the Internet have run through the Internet, but the network flow I wrote is inexplicable and WA…
1 /************************************************************** 2 Problem: 1001 3 User: mizersy 4 Language: C++ 5 Result: Wrong_Answer 6 ****************************************************************/ 7 8 #include <bits/stdc++.h> 9 using namespace std; 10 const int MAXN = 2000010; 11 const int MAXM = 6200010; 12 const int INF = 0x3f3f3f3f; 13 struct Edge{ 14 int to,next,cap,flow; 15 } edge[MAXM]; 16 int tol; 17 int head[MAXN]; 18 void init(){ 19 tol = 2; 20 memset(head,-1,sizeof(head)); 21 } 22 void addedge(int u,int v,int w,int rw = 0){ 23 edge[tol].to = v; 24 edge[tol].cap = w; 25 edge[tol].flow = 0; 26 edge[tol].next = head[u]; 27 head[u] = tol++; 28 edge[tol].to = u; 29 edge[tol].cap = rw; 30 edge[tol].flow = 0; 31 edge[tol].next = head[v]; 32 head[v] = tol++; 33 } 34 int Q[MAXN]; 35 int dep[MAXN],cur[MAXN],sta[MAXN]; 36 bool bfs(int s,int t,int n){ 37 int front = 0,tail = 0; 38 memset(dep,-1,sizeof(dep[0])*(n+1)); 39 dep[s] = 0; 40 Q[tail++] = s; 41 while(front < tail){ 42 int u = Q[front++]; 43 for(int i = head[u]; i !=-1; i = edge[i].next){ 44 int v = edge[i].to; 45 if(edge[i].cap > edge[i].flow && dep[v] ==-1){ 46 dep[v] = dep[u] + 1; 47 if(v == t) 48 return true; 49 Q[tail++] = v; 50 } 51 } 52 } 53 return false; 54 } 55 int dinic(int s,int t,int n){ 56 int maxflow = 0; 57 while(bfs(s,t,n)){ 58 for(int i = 0; i <= n; i++) cur[i] = head[i]; 59 int u = s, tail = 0; 60 while(cur[s] !=-1){ 61 if(u == t){ 62 int tp = INF; 63 for(int i = tail-1; i >= 0; i--) 64 tp = min(tp,edge[sta[i]].cap-edge[sta[i]].flow); 65 maxflow += tp; 66 for(int i = tail-1; i >= 0; i--){ 67 edge[sta[i]].flow += tp; 68 edge[sta[i]^1].flow-= tp; 69 if(edge[sta[i]].cap-edge[sta[i]].flow == 0) 70 tail = i; 71 } 72 u = edge[sta[tail]^1].to; 73 }else if(cur[u] !=-1 && edge[cur[u]].cap > edge[cur[u]].flow && dep[u] + 1 == dep[edge[cur[u]].to]) 74 { 75 sta[tail++] = cur[u]; 76 u = edge[cur[u]].to; 77 }else{ 78 while(u != s && cur[u] ==-1) 79 u = edge[sta[--tail]^1].to; 80 cur[u] = edge[cur[u]].next; 81 } 82 } 83 } 84 return maxflow; 85 } 86 int n,m,cnt; 87 int a[1005][1005]; 88 89 int point(int i,int j){ 90 return (i-1)*m+j; 91 } 92 93 int main(){ 94 scanf("%d%d",&n,&m); 95 cnt = 0; 96 init(); 97 memset(a,0,sizeof(a)); 98 for (int i = 1;i <= n;++i){ 99 for (int j = 1;j < m;++j){ 100 int w; scanf("%d",&w); 101 addedge(point(i,j),point(i,j+1),w); 102 } 103 } 104 for (int i = 1;i < n;++i){ 105 for (int j = 1;j <= m;++j){ 106 int w; scanf("%d",&w); 107 addedge(point(i,j),point(i+1,j),w); 108 } 109 } 110 for (int i = 1;i < n;++i){ 111 for (int j = 1;j < m;++j){ 112 int w; scanf("%d",&w); 113 addedge(point(i,j),point(i+1,j+1),w); 114 } 115 } 116 printf("%d\n",dinic(1,n*m,n*m)); 117 }
View Code
Because a graph is a plane graph, it can be turned into a dual graph. Then the shortest path of the dual graph is the minimum cut of the plane graph.It was a surprise. Last semester in the discrete class, I used to turn the plane map into the dual map, but I was in a hurry when I was in class. I didn’t think it was of any use and then I didn’t go deep into it. Surprisingly, duality diagrams still have this magical effect.But it’s easy to think about it.。
We need to be careful when constructing the dual graph.
1 /************************************************************** 2 Problem: 1001 3 User: mizersy 4 Language: C++ 5 Result: Accepted 6 Time:3108 ms 7 Memory:118480 kb 8 ****************************************************************/ 9 10 #include <bits/stdc++.h> 11 using namespace std; 12 const int MAXN = 2000005; 13 struct Edge{int to,next,w;}edge[MAXN*4]; 14 int tol,n,m,w; 15 int head[MAXN],vis[MAXN],dis[MAXN]; 16 void init(){ 17 tol = 0; 18 memset(vis,0,sizeof(vis)); 19 memset(dis,0x3f3f3f3f,sizeof(dis)); 20 memset(head,-1,sizeof(head)); 21 } 22 23 void addedge(int u,int v,int w){ 24 edge[tol] = Edge{v,head[u],w}; 25 head[u] = tol++; 26 edge[tol] = Edge{u,head[v],w}; 27 head[v] = tol++; 28 } 29 30 void getmap(){ 31 for (int j = 1;j < m;++j){ 32 scanf("%d",&w); 33 addedge(0,j*2,w); 34 } 35 for (int i = 2;i < n;++i){ 36 for (int j = 1;j < m;++j){ 37 scanf("%d",&w); 38 addedge(2*(i-2)*(m-1)+j*2-1,2*(i-1)*(m-1)+j*2,w); 39 } 40 } 41 if (n >= 2) 42 for (int j = 1;j < m;++j){ 43 scanf("%d",&w); 44 addedge(2*(n-2)*(m-1)+j*2-1,2*(n-1)*(m-1)+1,w); 45 } 46 for (int i = 1;i < n;++i){ 47 for (int j = 1;j <= m;++j){ 48 scanf("%d",&w); 49 if (j == 1) addedge(2*(n-1)*(m-1)+1,2*(i-1)*(m-1)+1,w); 50 else if (j == m) addedge(2*i*(m-1),0,w); 51 else addedge(2*(i-1)*(m-1)+(j-1)*2,2*(i-1)*(m-1)+(j-1)*2+1,w); 52 } 53 } 54 55 for (int i = 1;i < n;++i){ 56 for (int j = 1;j < m;++j){ 57 scanf("%d",&w); 58 addedge(2*(i-1)*(m-1)+(j-1)*2+1,2*(i-1)*(m-1)+j*2,w); 59 } 60 } 61 } 62 63 int spfa(int s,int t){ 64 queue <int> q; 65 dis[s] = 0; vis[s] = 1; 66 q.push(s); 67 while(!q.empty()){ 68 int u = q.front(); q.pop(); 69 vis[u] = 0; 70 for (int i = head[u];i != -1;i = edge[i].next){ 71 int v = edge[i].to,w = edge[i].w; 72 if (dis[v] > dis[u] + w){ 73 dis[v] = dis[u] + w; 74 if (!vis[v]){ 75 vis[v] = 1; 76 q.push(v); 77 } 78 } 79 } 80 } 81 return dis[t]; 82 } 83 84 int main(){ 85 init(); 86 scanf("%d%d",&n,&m); 87 if (n == 1 || m == 1){ 88 if (n > m) swap(n,m); 89 int ans = 0x3f3f3f3f; 90 for (int i = 1;i < m;++i){ 91 scanf("%d",&w); 92 ans = min(ans,w); 93 } 94 if (ans == 0x3f3f3f3f) ans = 0; 95 printf("%d\n",ans); 96 return 0; 97 } 98 getmap(); 99 printf("%d\n",spfa(0,2*(m-1)*(n-1)+1)); 100 return 0; 101 }