BZOJ1001或洛谷4001 [BJOI2006]狼抓兔子

显然就是求最小割。
而对于一个平面图有结论，最大流=最小割=对偶图最短路。
所以这题可用最大流或是转换为对偶图求最短路，这里我是用的对偶图。
虽然理论上按上界算，这题\(Dinic\)应该是跑不过去的，不过因为网络流复杂度玄学，\(Dinic\)莫名跑得挺快的。
在转换对偶图的时候，注意\(n = 1\)或\(m = 1\)的情况。

#include<cstdio>#include<cstring>#include<queue>using namespace std;const int N = 2e6   10;const int M = 7e6   10;struct po {    int x, d;    bool operator < (const po &b) const    {        return d > b.d;    }};po X;int fi[N], di[M], ne[M], da[M], dis[N], l, st, ed, n, m;bool v[N];priority_queue<po>q;inline int re(){    int x = 0;    char c = getchar();    bool p = 0;    for (; c < '0' || c > '9'; c = getchar())        p |= c == '-';    for (; c >= '0' && c <= '9'; c = getchar())        x = x * 10   c - '0';    return p ? -x : x;}inline void add(int x, int y, int z){    di[  l] = y;    da[l] = z;    ne[l] = fi[x];    fi[x] = l;    di[  l] = x;    da[l] = z;    ne[l] = fi[y];    fi[y] = l;}inline int ch(int x, int y, int L){    int k = ((x - 1) * (m - 1)   y) << 1;    return L ? k - 1 : k;}inline void add_row(int x, int y, int z){    if (!(x ^ 1))        add(ch(x, y, 0), ed, z);    else        if (!(x ^ n))            add(st, ch(x - 1, y, 1), z);        else            add(ch(x - 1, y, 1), ch(x, y, 0), z);}inline void add_col(int x, int y, int z){    if (!(y ^ 1))        add(st, ch(x, y, 1), z);    else        if (!(y ^ m))            add(ch(x, y - 1, 0), ed, z);        else            add(ch(x, y - 1, 0), ch(x, y, 1), z);}inline void add_opl(int x, int y, int z){    add(ch(x, y, 1), ch(x, y, 0), z);}int main(){    int i, j, x, y;    n = re();    m = re();    st = (n - 1) * (m - 1) << 1 | 1;    ed = st   1;    if (!(n ^ 1) || !(m ^ 1))    {        for (i = 1; i <= n; i  )            for (j = 1; j < m; j  )                add(st, ed, re());        for (i = 1; i < n; i  )            for (j = 1; j <= m; j  )                add(st, ed, re());        for (i = 1; i < n; i  )            for (j = 1; j < m; j  )                add(st, ed, re());    }    else    {        for (i = 1; i <= n; i  )            for (j = 1; j < m; j  )                add_row(i, j, re());        for (i = 1; i < n; i  )            for (j = 1; j <= m; j  )                add_col(i, j, re());        for (i = 1; i < n; i  )            for (j = 1; j < m; j  )                add_opl(i, j, re());    }    memset(dis, 60, sizeof(dis));    X.d = dis[X.x = st] = 0;    q.push(X);    while (!q.empty())    {        x = q.top().x;        q.pop();        if (v[x])            continue;        v[x] = 1;        for (i = fi[x]; i; i = ne[i])            if (dis[X.x = y = di[i]] > dis[x]   da[i])            {                X.d = dis[y] = dis[x]   da[i];                q.push(X);            }    }    printf("%d", dis[ed]);    return 0;}