这几天敲了几道最大流的问题，发现网络流真是模板算法啊。。。。
敲来敲去敲了几遍，基本每遍都敲得让人灰心，但同时也感受到了网络流的强大所在，这是我做网络流的第一题，，本以为看了一遍小白书的代码差不多理解就可以A掉一题的，没想到打击不是一点点的少啊。。。。。
首先小白书将的邻接矩阵存边，这里必须用邻接表，而本以为随便改改就好的，没想到那个记录路径却让人头疼得要命，无赖之下看了题解，看到了一个名为SAP的强大算法，虽然比小白的代码量增加了不少，理解起来也不是很容易，但是复杂度真心减少了不知一点点啊！！！！
虽然履步维艰，最后慢慢看着大牛模板一点一点敲了出来，可是其实还不是特别的了解的说，只是大致明白了思路而已，没办法看不懂就背下来吧，相信敲得多了自然就会慢慢理解记住的。。。
下面的SAP代码风格是我在网上找了一些后自己最觉得满意的一种（看到很多人使用loop；goto语句，真心不想用那样的句子啊，真心强迫症患者啊。。。。）
(能有自己的网络流模板感觉真好~~~)
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define inf ((LL)1<<40)
#define lson k<<1, L, mid
#define rson k<<1|1, mid+1, R
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a, b) memset(a, b, sizeof(a))
#define FOPENIN(IN) freopen(IN, "r", stdin)
#define FOPENOUT(OUT) freopen(OUT, "w", stdout)
template<class T> T ABS ( T a) { return a >= ? a : -a; }
template<class T> T CMP_MIN ( T a, T b ) { return a < b; }
template<class T> T CMP_MAX ( T a, T b ) { return a > b; }
template<class T> T MAX ( T a, T b ) { return a > b ? a : b; }
template<class T> T MIN ( T a, T b ) { return a < b ? a : b; }
template<class T> T GCD ( T a, T b ) { return b ? GCD ( b, a % b ) : a; }
template<class T> T LCM ( T a, T b ) { return a / GCD ( a, b ) * b; }
template<class T> void SWAP( T& a, T& b ) { T t = a; a = b; b = t; } typedef __int64 LL;
//typedef long long LL;
const int MAXN = ;
const int MAXM = ;
const double eps = 1e-;
const double PI = 4.0 * atan(1.0);
const LL MOD = ; int dx[] = {, -, , };
int dy[] = {, , -, }; int n, m, k, ma[][], mus[][], sum; struct Edge { int to, cap, next; }edge[MAXM<<];
int head[MAXN], tot; int src, des;
int dep[MAXN], gap[MAXN], pre[MAXN], aug[MAXN], cur[MAXN]; void init()
{
int x, y;
mem0(mus); mem0(edge);sum = ;
for(int i = ; i <= n; i ++)
{
for(int j = ; j <= m; j ++ )
{
scanf("%d", &ma[i][j]);
sum += ma[i][j];
}
}
for(int i = ; i < k; i ++)
{
scanf("%d %d", &x, &y);
mus[x][y] = ;
}
} void addEdge(int u, int v, int val)
{
edge[tot].to = v; edge[tot].cap = val; edge[tot].next= head[u];
head[u] = tot ++;
edge[tot].to = u; edge[tot].cap = ; edge[tot].next = head[v];
head[v] = tot ++;
} void init_Edge()
{
mem1(head); tot = ;
src = ; des = m * n + ;
for(int i = ; i <= n; i ++)
{
for(int j = ; j <= m; j ++)
{
int now = (i-)*m + j;
if((i+j)&){
if(mus[i][j]) addEdge(now, des, INF);
else addEdge(now, des, ma[i][j]);
}
else {
if(mus[i][j]) addEdge(src, now, INF);
else addEdge(src, now, ma[i][j]);
for(int k = ; k < ; k ++ ) {
int nx = i + dx[k], ny = j + dy[k];
if(nx> && nx<=n && ny> && ny<=m)
addEdge(now, (nx-)*m+ny, *(ma[i][j]&ma[nx][ny]));
}
}
}
}
} int SAP(int n)
{
mem0(aug); mem0(pre);
mem(dep, ); mem(gap, );
int max_flow = , u = src;
aug[src] = INF;
pre[src] = -;
gap[] = n;
for(int i = ; i <= n; i ++)
cur[i] = head[i];
while(dep[src] < n)
{
//printf("%d\n", u);
if(u == des)
{
// printf("%d\n", max_flow);
max_flow += aug[des];
for(int v = pre[des]; v != -; v = pre[v])
{
int e = cur[v];
edge[e].cap -= aug[des];
edge[e^].cap += aug[des];
aug[v] -= aug[des];
if(edge[e].cap == ) u = v;
//u = src;
}
}
int flag = ;
for(int e = cur[u]; e != -; e = edge[e].next)
{
int v = edge[e].to;
if(edge[e].cap > && dep[u] == dep[v] + )
{
flag = ;
pre[v] = u; cur[u] = e;
aug[v] = MIN(aug[u], edge[e].cap);
u = v;
break;
}
}
if(!flag)
{
if(--gap[dep[u]] == )
break;
int min_dep = n;
cur[u] = head[u];
for(int e = head[u]; e != -; e = edge[e].next)
{
int v = edge[e].to;
if(edge[e].cap > && dep[v] < min_dep)
{
min_dep = dep[v];
cur[u] = e;
}
}
dep[u] = min_dep + ;
gap[dep[u]] ++;
if(u != src) u = pre[u];
}
}
return max_flow;
} int main()
{
while(~scanf("%d %d %d", &n, &m, &k))
{
init();
init_Edge();
printf("%d\n", sum - SAP(des+));
}
return ;
}