二次联通门 :
lqz已经废了
/* BZOJ 1001: [BeiJing2006]狼抓兔子 最小割*/#include#include #include #define rg registerinline void read (int &n) { rg char c = getchar (); for (n = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); n = n * 10 + c - '0', c = getchar ());}inline int min (int a, int b) { return a < b ? a : b; }int S, T;namespace net { const int Max = 1000006; int _v[Max * 6], _n[Max * 6], list[Max], _f[Max * 6], EC = 1; int q[Max * 6]; inline void In (int u, int v, int f) { _v[++ EC] = v, _n[EC] = list[u], list[u] = EC, _f[EC] = f; _v[++ EC] = u, _n[EC] = list[v], list[v] = EC, _f[EC] = f; } int d[Max]; bool Bfs () { int h = 0, t = 1; q[h] = S; rg int i, n; for (i = 0; i <= T; ++ i) d[i] = -1; for (d[S] = 0; h < t; ++ h) { n = q[h]; for (i = list[n]; i; i = _n[i]) if (_f[i] && d[_v[i]] == -1) { d[_v[i]] = d[n] + 1, q[t ++] = _v[i]; if (_v[i] == T) return true; } } return false; } int Flowing (int n, int f) { if (n == T || f == 0) return f; int p, r = 0; for (rg int i = list[n]; i; i = _n[i]) if (d[_v[i]] == d[n] + 1 && _f[i]) { p = Flowing (_v[i], min (f, _f[i])); if (p > 0) { r += p, f -= p, _f[i] -= p, _f[i ^ 1] += p; if (f == 0) return r; } } if (r != f) d[n] = -1; return r; }#define INF 1000000000 inline int Dinic (int S, int T) { int Answer = 0; for (; Bfs (); Answer += Flowing (S, INF)); return Answer; }}int main (int argc, char *argv[]) { int N, M, x; read (N), read (M); rg int i, j; for (i = 1; i <= N; ++ i) for (j = 1; j < M; ++ j) read (x), net :: In ((i - 1) * M + j, (i - 1) * M + j + 1, x); for (i = 1; i < N; ++ i) for (j = 1; j <= M; ++ j) read (x), net :: In ((i - 1) * M + j, i * M + j, x); for (i = 1; i < N; ++ i) for (j = 1; j < M; ++ j) read (x), net :: In ((i - 1) * M + j, i * M + j + 1, x); S = 1, T = N * M; printf ("%d", net :: Dinic (S, T)); return 0;}