HYSBZ_1001
建好图之后求最小割即可。
#include#include #define MAXD 1000100 #define MAXM 6000600 #define INF 1000000000 int N, M, T, e, first[MAXD], next[MAXM], u[MAXM], v[MAXM], flow[MAXM]; int q[MAXD], d[MAXD], work[MAXD], s[MAXD]; void add(int a, int b, int f) { u[e] = a; v[e] = b; flow[e] = f; next[e] = first[a]; first[a] = e; e ++; } void init() { int i, j, a, b, f; T = N * M - 1; e = 0; for(i = 0; i <= T; i ++) first[i] = -1; for(i = 0; i < N; i ++) for(j = 1; j < M; j ++) { scanf("%d", &f); a = i * M + j - 1; b = i * M + j; add(a, b, f); add(b, a, f); } for(i = 1; i < N; i ++) for(j = 0; j < M; j ++) { scanf("%d", &f); a = (i - 1) * M + j; b = i * M + j; add(a, b, f); add(b, a, f); } for(i = 1; i < N; i ++) for(j = 1; j < M; j ++) { scanf("%d", &f); a = (i - 1) * M + j - 1; b = i * M + j; add(a, b, f); add(b, a, f); } } int bfs() { int i, j, rear; for(i = 1; i <= T; i ++) d[i] = -1; d[0] = 0; rear = 0; q[rear ++] = 0; for(i = 0; i < rear ; i ++) for(j = first[q[i]]; j != -1; j = next[j]) if(flow[j] && d[v[j]] == -1) { d[v[j]] = d[q[i]] + 1; if(v[j] == T) return 1; q[rear ++] = v[j]; } return 0; } int dinic() { int i, j, cur, r, res = 0; while(bfs()) { r = 0; cur = 0; for(i = 0; i <= T; i ++) work[i] = first[i]; for(;;) { if(cur == T) { int a = INF, minr = r; for(i = 0; i < r; i ++) if(flow[s[i]] < a) { a = flow[s[i]]; minr = i; } for(i = 0; i < r; i ++) { flow[s[i]] -= a; flow[s[i] ^ 1] += a; } r = minr; cur = u[s[r]]; res += a; } for(i = work[cur]; i != -1; i = next[i]) if(flow[i] && d[v[i]] == d[cur] + 1) break; work[cur] = i; if(i != -1) { s[r ++] = i; cur = v[i]; } else { d[cur] = -1; if(r == 0) break; r --; cur = u[s[r]]; } } } return res; } int main() { while(scanf("%d%d", &N, &M) == 2) { init(); int res = dinic(); printf("%d\n", res); } return 0; }