[BJOI 2006] 늑대가 토끼를 잡는다.

제목 링크

[비주2006] 늑대가 토끼를 잡는다.

문제풀이

분명히 주어진 그림의 최소 할을 구하는 것이다.하지만 최대 흐름을 바로 달리면 폭발한다.
우리는 이 그림이 하나의 성질을 가지고 있다는 것을 발견했다. 그것은 평면도이다.우리는 그것의 대구도를 구성하는 것을 고려한다. 왜냐하면 대구도의 최단길은 바로 원도의 최소할이기 때문이다.구체적인 구도 방법은 코드를 보십시오.

코드

#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 2000005;
const int maxm = 6000005;
char ch;
bool vis[maxn];
int n, m, x, ret, dis[maxn];
int tot, ter[maxm], nxt[maxm], len[maxm], lnk[maxn];
int read() {
    ch = getchar();
    ret = 0;
    while (!isdigit(ch)) {
        ch = getchar();
    }
    while (isdigit(ch)) {
        ret = (ret << 1) + (ret << 3) + (ch ^ '0');
        ch = getchar();
    }
    return ret;
}
int id(int i, int j, int k) {
    if (i > n || j < 1) {
        return 0;
    }
    if (i < 1 || j > m) {
        return n * m << 1 | 1;
    }
    return (i - 1) * m + j + k * n * m;
}
void adde(int u, int v, int w) {
    ter[tot] = v;
    len[tot] = w;
    nxt[tot] = lnk[u];
    lnk[u] = tot++;
}
int spfa(int s, int t) {
    queue<int> que;
    que.push(s);
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = s, vis[s] = 1;
    for (int u, v, w; !que.empty(); ) {
        u = que.front();
        que.pop();
        vis[u] = 0;
        for (int i = lnk[u]; ~i; i = nxt[i]) {
            v = ter[i], w = len[i];
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!vis[v]) {
                    vis[v] = 1;
                    que.push(v);
                }
            }
        }
    }
    return dis[t];
}
int main() {
    memset(lnk, -1, sizeof(lnk));
    n = read(), m = read(), n--, m--;
    for (int i = 1; i <= n + 1; i++) {
        for (int j = 1; j <= m; j++) {
            x = read();
            adde(id(i, j, 1), id(i - 1, j, 0), x);
            adde(id(i - 1, j, 0), id(i, j, 1), x);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m + 1; j++) {
            x = read();
            adde(id(i, j, 0), id(i, j - 1, 1), x);
            adde(id(i, j - 1, 1), id(i, j, 0), x);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            x = read();
            adde(id(i, j, 0), id(i, j, 1), x);
            adde(id(i, j, 1), id(i, j, 0), x);
        }
    }
    printf("%d
", spfa(0, n * m << 1 | 1));
    return 0;
}

총결산

평면도(통상 격자도)의 최소 할(최대 흐름)을 요구하고 데이터 범위가 넓어야 한다면 우리는 본 문제의 기교를 사용하여 문제를 구해야 한다.