zoj 3475 The Great Wall I

zoj 3475 The Great Wall I

#include <iostream>#include<stdio.h>#include<memory.h>#include<vector>using namespace std;#define Inf 0x7ffffffstruct point {int l, r, u, d;};struct noode {int x, y, s;} p[10];point map[30][30];int n, m, i, j, k, x, ans, netcost, op;#define N 30009struct node {int t;int flow;int cap;int index;};vector<node> g[N];vector<int> e[N];int rank[N];void init(int n) {memset(rank, -1, sizeof(rank));int i;for (i = 0; i < n; ++i) {g[i].clear();e[i].clear();}}void addedge(int a, int b, int c) {node temp;temp.t = b;temp.cap = c;temp.flow = 0;temp.index = g[b].size();g[a].push_back(temp);temp.t = a;temp.cap = 0;temp.index = g[a].size() - 1;g[b].push_back(temp);}void addedge1(int a, int b, int c) {node temp;temp.t = b;temp.cap = c;temp.flow = 0;temp.index = g[b].size();g[a].push_back(temp);temp.t = a;temp.index = g[a].size() - 1;g[b].push_back(temp);}int bfs(int s, int t, int n) {memset(rank, -1, sizeof(rank));int i;for (i = 0; i < n; ++i)e[i].clear();int que[N];int u, v;int front = 0, rear = 0;rank[s] = 0;rear++;que[front] = s;for (; rear > front;) {u = que[front++];for (i = 0; i < g[u].size(); ++i) {v = g[u][i].t;if (rank[v] == -1 && g[u][i].cap) {que[rear++] = v;rank[v] = rank[u] + 1;}if (rank[v] == rank[u] + 1)e[u].push_back(i);}}return (rank[t] != -1);}int dinic(int s, int t, int n) {int st[N], maxflow = 0;int aux[N];int top, cur;int p, i, k;while (1) {if (bfs(s, t, n) == 0)break;top = 0;st[top] = s;cur = s;while (1) {if (cur == t) {int minc = 0x7fffffff;for (i = 0; i < top; ++i) {p = aux[i + 1];if (minc > g[st[i]][p].cap)minc = g[st[i]][p].cap, k = i;}for (i = 0; i < top; ++i) {p = aux[i + 1];g[st[i]][p].cap -= minc;g[g[st[i]][p].t][g[st[i]][p].index].cap += minc;}maxflow += minc;cur = st[top = k];}int len = e[cur].size();while (len) {p = e[cur][len - 1];if (g[cur][p].cap && rank[g[cur][p].t] == rank[cur] + 1)break;else {len--;e[cur].pop_back();}}if (len) {cur = st[++top] = g[cur][p].t;aux[top] = p;} else {if (top == 0)break;rank[cur] = -1;cur = st[--top];}}}return maxflow;}void solve() {int res = 0;int i, j;init(n * m + 2 * n + 2 * m + 2);for (i = 1; i <= k; i++) {if (p[i].s > 0) {if ((1 << (i - 1)) & (op)) {addedge(0, (p[i].x - 1) * m + p[i].y, Inf);res += p[i].s;}} else if (p[i].s == 0)addedge(0, (p[i].x - 1) * m + p[i].y, Inf);elseaddedge((p[i].x - 1) * m + p[i].y, n * m + 2 * n + 2 * m + 1, Inf);}for (i = 1; i <= n; i++)for (j = 1; j <= m; j++) {if (i < n) {addedge1((i - 1) * m + j, (i) * m + j, map[i][j].d);}if (j < m) {addedge1((i - 1) * m + j, (i - 1) * m + j + 1, map[i][j].r);}}for (j = 1; j <= m; j++) {addedge1(j, n * m + j, map[1][j].u);addedge1(n * m + j, n * m + 2 * n + 2 * m + 1, Inf);addedge1((n - 1) * m + j, n * m + m + j, map[n][j].d);addedge(n * m + m + j, n * m + 2 * n + 2 * m + 1, Inf);}for (i = 1; i <= n; i++) {addedge1((i - 1) * m + 1, n * m + 2 * m + i, map[i][1].l);addedge1(n * m + 2 * m + i, n * m + 2 * n + 2 * m + 1, Inf);addedge1((i - 1) * m + m, n * m + 2 * m + n + i, map[i][m].r);addedge1(n * m + 2 * m + n + i, n * m + 2 * n + 2 * m + 1, Inf);}ans = min(ans,dinic(0, n * m + 2 * n + 2 * m + 1, n * m + 2 * n + 2 * m + 2)- res);}void dfs() {for (op = 0; op < (1 << k); op++) {solve();}}int main() {while (scanf("%d%d", &n, &m) != EOF) {for (j = 1; j <= m; j++) {scanf("%d", &x);map[1][j].u = x;}for (i = 1; i <= n; i++) {for (j = 1; j <= m + 1; j++) {scanf("%d", &x);map[i][j].l = x;map[i][j - 1].r = x;}for (j = 1; j <= m; j++) {scanf("%d", &x);map[i][j].d = x;map[i + 1][j].u = x;}}scanf("%d", &k);for (i = 1; i <= k; i++) {scanf("%d%d%d", &p[i].s, &p[i].x, &p[i].y);p[i].x++;p[i].y++;}ans = Inf;dfs();printf("%dn", ans);}return 0;}