洛谷4001 狼抓兔子

平面图最小割转对偶图最短路。

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 2e6 + 10;
const int_t SOURCE = 2e6 + 1;
const int_t SINK = 2e6 + 2;
const int_t INF = 0x3fffffffffffffff;
int n, m;
struct Edge {
    int to, weight;
};

std::vector<Edge> graph[LARGE + 1];

int_t dis[LARGE + 1];
bool visited[LARGE + 1];

void pushEdge(int from, int to, int weight) {
    graph[from].push_back(Edge{to, weight});
    graph[to].push_back(Edge{from, weight});
#ifdef DEBUG
    cout << "edge " << from << "," << to << "," << weight << endl;
#endif
}
int_t encode(int_t r, int_t c) { return (r - 1) * m + c; }
int main() {
    std::ios::sync_with_stdio(false);
    cin >> n >> m;
    if (m == 1) {
        int_t val = INF;
        for (int_t i = 1; i <= n; i++) {
            int_t x;
            cin >> x;
            val = std::min(val, x);
        }
        cout << val << endl;
        return 0;
    }
    for (int_t i = 1; i <= n; i++) {
        for (int_t j = 1; j < m; j++) {
#ifdef DEBUG
            cout << i << "," << j << endl;
#endif
            int_t val;
            cin >> val;
            if (i == 1) {
                pushEdge(2 * encode(i, j) + 1, SINK, val);
            }
            if (i == n) {
                pushEdge(SOURCE, 2 * encode(i - 1, j), val);
            }

            if (i != 1 && i != n) {
                pushEdge(encode(i, j) * 2 + 1, encode(i - 1, j) * 2, val);
            }
        }
    }
    for (int_t i = 1; i < n; i++) {
        for (int_t j = 1; j <= m; j++) {
            int_t val;
            cin >> val;
            if (j == 1) {
                pushEdge(SOURCE, 2 * encode(i, j), val);
            }
            if (j == m) {
                pushEdge(encode(i, j - 1) * 2 + 1, SINK, val);
            }
            if (j != 1 && j != m) {
                pushEdge(encode(i, j - 1) * 2 + 1, encode(i, j) * 2, val);
            }
        }
    }
    for (int_t i = 1; i < n; i++) {
        for (int_t j = 1; j < m; j++) {
            int_t val;
            cin >> val;
            pushEdge(encode(i, j) * 2, encode(i, j) * 2 + 1, val);
        }
    }
    std::fill(dis, dis + 1 + LARGE, INF);
    struct Pair {
        int_t vtx, dis;
        bool operator>(const Pair& p) const { return dis > p.dis; }
    };
    std::priority_queue<Pair, std::vector<Pair>, std::greater<Pair> > heap;
    heap.push(Pair{SOURCE, 0});
    dis[SOURCE] = 0;
    while (heap.empty() == false) {
        int front = heap.top().vtx;
        heap.pop();
        if (visited[front]) continue;
        visited[front] = true;
#ifdef DEBUG
        cout << "poping " << front << endl;
#endif
        for (const Edge& edge : graph[front]) {
            dis[edge.to] = std::min(dis[edge.to], dis[front] + edge.weight);
            heap.push(Pair{edge.to, dis[edge.to]});
        }
    }
    cout << dis[SINK] << endl;
    return 0;
}