HDU3657Game（最大流）

这几天敲了几道最大流的问题，发现网络流真是模板算法啊。。。。

敲来敲去敲了几遍，基本每遍都敲得让人灰心，但同时也感受到了网络流的强大所在，这是我做网络流的第一题，，本以为看了一遍小白书的代码差不多理解就可以A掉一题的，没想到打击不是一点点的少啊。。。。。

首先小白书将的邻接矩阵存边，这里必须用邻接表，而本以为随便改改就好的，没想到那个记录路径却让人头疼得要命，无赖之下看了题解，看到了一个名为SAP的强大算法，虽然比小白的代码量增加了不少，理解起来也不是很容易，但是复杂度真心减少了不知一点点啊！！！！

虽然履步维艰，最后慢慢看着大牛模板一点一点敲了出来，可是其实还不是特别的了解的说，只是大致明白了思路而已，没办法看不懂就背下来吧，相信敲得多了自然就会慢慢理解记住的。。。

下面的SAP代码风格是我在网上找了一些后自己最觉得满意的一种（看到很多人使用loop；goto语句，真心不想用那样的句子啊，真心强迫症患者啊。。。。）

(能有自己的网络流模板感觉真好~~~)

  1 #include <map>
  2 #include <set>
  3 #include <stack>
  4 #include <queue>
  5 #include <cmath>
  6 #include <ctime>
  7 #include <vector>
  8 #include <cstdio>
  9 #include <cctype>
 10 #include <cstring>
 11 #include <cstdlib>
 12 #include <iostream>
 13 #include <algorithm>
 14 using namespace std;
 15 #define INF 0x3f3f3f3f
 16 #define inf ((LL)1<<40)
 17 #define lson k<<1, L, mid
 18 #define rson k<<1|1, mid+1, R
 19 #define mem0(a) memset(a,0,sizeof(a))
 20 #define mem1(a) memset(a,-1,sizeof(a))
 21 #define mem(a, b) memset(a, b, sizeof(a))
 22 #define FOPENIN(IN) freopen(IN, "r", stdin)
 23 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)
 24 template<class T> T ABS ( T a) { return a >= 0 ? a : -a;   }
 25 template<class T> T CMP_MIN ( T a, T b ) { return a < b;   }
 26 template<class T> T CMP_MAX ( T a, T b ) { return a > b;   }
 27 template<class T> T MAX ( T a, T b ) { return a > b ? a : b; }
 28 template<class T> T MIN ( T a, T b ) { return a < b ? a : b; }
 29 template<class T> T GCD ( T a, T b ) { return b ? GCD ( b, a % b ) : a; }
 30 template<class T> T LCM ( T a, T b ) { return a / GCD ( a, b ) * b;     }
 31 template<class T> void SWAP( T& a, T& b ) { T t = a; a = b;  b = t;     }
 32 
 33 typedef __int64 LL;
 34 //typedef long long LL;
 35 const int MAXN = 101000;
 36 const int MAXM = 500100;
 37 const double eps = 1e-14;
 38 const double PI = 4.0 * atan(1.0);
 39 const LL MOD = 1000000007;
 40 
 41 int dx[4] = {0, -1, 0, 1};
 42 int dy[4] = {1, 0, -1, 0};
 43 
 44 int n, m, k, ma[55][55], mus[55][55], sum;
 45 
 46 struct Edge { int to, cap, next; }edge[MAXM<<1];
 47 int head[MAXN], tot;
 48 
 49 int src, des;
 50 int dep[MAXN], gap[MAXN], pre[MAXN], aug[MAXN], cur[MAXN];
 51 
 52 void init()
 53 {
 54     int x, y;
 55     mem0(mus); mem0(edge);sum = 0;
 56     for(int i = 1; i <= n; i ++)
 57     {
 58         for(int j = 1; j <= m; j ++ )
 59         {
 60             scanf("%d", &ma[i][j]);
 61             sum += ma[i][j];
 62         }
 63     }
 64     for(int i = 0; i < k; i ++)
 65     {
 66         scanf("%d %d", &x, &y);
 67         mus[x][y] = 1;
 68     }
 69 }
 70 
 71 void addEdge(int u, int v, int val)
 72 {
 73     edge[tot].to = v; edge[tot].cap = val;   edge[tot].next= head[u];
 74     head[u] = tot ++;
 75     edge[tot].to = u; edge[tot].cap = 0;     edge[tot].next = head[v];
 76     head[v] = tot ++;
 77 }
 78 
 79 void init_Edge()
 80 {
 81     mem1(head); tot = 0;
 82     src = 0; des = m * n + 1;
 83     for(int i = 1; i <= n; i ++)
 84     {
 85         for(int j = 1; j <= m; j ++)
 86         {
 87             int now = (i-1)*m + j;
 88             if((i+j)&1){
 89                 if(mus[i][j]) addEdge(now, des, INF);
 90                 else addEdge(now, des, ma[i][j]);
 91             }
 92             else {
 93                 if(mus[i][j]) addEdge(src, now, INF);
 94                 else addEdge(src, now, ma[i][j]);
 95                 for(int k = 0; k < 4; k ++ ) {
 96                     int nx = i + dx[k], ny = j + dy[k];
 97                     if(nx>0 && nx<=n && ny>0 && ny<=m)
 98                         addEdge(now, (nx-1)*m+ny, 2*(ma[i][j]&ma[nx][ny]));
 99                 }
100             }
101         }
102     }
103 }
104 
105 int SAP(int n)
106 {
107     mem0(aug);   mem0(pre);
108     mem(dep, 0); mem(gap, 0);
109     int max_flow = 0, u = src;
110     aug[src] = INF;
111     pre[src] = -1;
112     gap[0] = n;
113     for(int i = 0; i <= n; i ++)
114         cur[i] = head[i];
115     while(dep[src] < n)
116     {
117         //printf("%d
", u);
118         if(u == des)
119         {
120           //  printf("%d
", max_flow);
121             max_flow += aug[des];
122             for(int v = pre[des]; v != -1; v = pre[v])
123             {
124                 int e = cur[v];
125                 edge[e].cap   -= aug[des];
126                 edge[e^1].cap += aug[des];
127                 aug[v] -= aug[des];
128                 if(edge[e].cap == 0) u = v;
129                 //u = src;
130             }
131         }
132         int flag = 0;
133         for(int e = cur[u]; e != -1; e = edge[e].next)
134         {
135             int v = edge[e].to;
136             if(edge[e].cap > 0 && dep[u] == dep[v] + 1)
137             {
138                 flag = 1;
139                 pre[v] = u; cur[u] = e;
140                 aug[v] = MIN(aug[u], edge[e].cap);
141                 u = v;
142                 break;
143             }
144         }
145         if(!flag)
146         {
147             if(--gap[dep[u]] == 0)
148                 break;
149             int min_dep = n;
150             cur[u] = head[u];
151             for(int e = head[u]; e != -1; e = edge[e].next)
152             {
153                 int v = edge[e].to;
154                 if(edge[e].cap > 0 && dep[v] < min_dep)
155                 {
156                     min_dep = dep[v];
157                     cur[u] = e;
158                 }
159             }
160             dep[u] = min_dep + 1;
161             gap[dep[u]] ++;
162             if(u != src) u = pre[u];
163         }
164     }
165     return max_flow;
166 }
167 
168 int main()
169 {
170     while(~scanf("%d %d %d", &n, &m, &k))
171     {
172         init();
173         init_Edge();
174         printf("%d
", sum - SAP(des+1));
175     }
176     return 0;
177 }