BZOJ1001 [BeiJing2006]狼抓兔子 平面图转对偶图，最小割转最短路

  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 }