/*************************************************************************************** 去年网络赛的一道题,现在看来也不是很难。做个HDU上那道方格取数的话,这道题大致就有想法了, 但这道题有个问题是,必选点的处理,我的做法是如果该点为偶数点,则在源点与该点间建一条流量为oo 的边,如果该点为奇数点,则在该点与汇点间建一条流量为oo的边,这样就完美解决了必选点的问题,然 后就是用dinic求最大流,最后结果取反即可。1Y~ ***************************************************************************************/ #include <iostream> #include <cstring> #include <memory> #include <cstdio> #include <queue> using namespace std; const int MAXN = 52; const int MAXV = MAXN * MAXN; const int MAXE = MAXV * 6; const int oo = 0x3f3f3f3f; struct Edges { int end; int flow; int next; }edges[MAXE]; int n, m, k, ecnt, head[MAXV], data[MAXN][MAXN]; int lev[MAXV]; bool sign[MAXN][MAXN]; const int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; inline void add_edge(int u, int v, int f) { //printf("edge: u = %d, v = %d, f = %d\n", u, v, f); edges[ecnt].end = v; edges[ecnt].flow = f; edges[ecnt].next = head[u]; head[u] = ecnt++; edges[ecnt].end = u; edges[ecnt].flow = 0; edges[ecnt].next = head[v]; head[v] = ecnt++; return ; } inline bool allow(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; } void init() { ecnt = 0; memset(head, -1, sizeof(head)); memset(sign, false, sizeof(sign)); return ; } bool bfs(int src, int sink) { int crt, nxt, val; queue<int>Q; memset(lev, -1, sizeof(lev)); lev[src] = 0; Q.push(src); while (!Q.empty()) { crt = Q.front(); Q.pop(); for (int i = head[crt]; i != -1; i = edges[i].next) { nxt = edges[i].end; val = edges[i].flow; if (-1 == lev[nxt] && val > 0) { lev[nxt] = lev[crt] + 1; Q.push(nxt); } } } return (lev[sink] != -1); } int dfs(int crt, int sink, int flow) { if (crt == sink) { return flow; } int nxt, val; int tf = 0, f; for (int i = head[crt]; i != -1; i = edges[i].next) { nxt = edges[i].end; val = edges[i].flow; if (lev[nxt] == lev[crt] + 1 && val > 0 && tf < flow && (f = dfs(nxt, sink, min(val, flow - tf)))) { edges[i].flow -= f; edges[i ^ 1].flow += f; tf += f; } } return tf; } int dinic(int src, int sink) { int res = 0; while (bfs(src, sink)) { res += dfs(src, sink, oo); } return res; } void ace() { int src, sink, a, b; int u, v; int res; while (scanf("%d %d %d", &n, &m, &k) != EOF) { init(); src = n * m; sink = src + 1; res = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { scanf("%d", &data[i][j]); res += data[i][j]; } } while (k--) { scanf("%d %d", &a, &b); --a; --b; sign[a][b] = true; } for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { u = i * m + j; if (~(i + j) & 0x1) { add_edge(src, u, sign[i][j] ? oo : data[i][j]); for (int k = 0; k < 4; ++k) { int ti = i + dir[k][0], tj = j + dir[k][1]; if (!allow(ti, tj)) { continue ; } v = ti * m + tj; add_edge(u, v, (data[i][j] & data[ti][tj]) << 1); } } else { add_edge(u, sink, sign[i][j] ? oo : data[i][j]); } } } int buf = dinic(src, sink); //printf("buf:%d\n", buf); printf("%d\n", res - buf); } return ; } int main() { ace(); return 0; }