洛谷P4001 [ICPC-Beijing 2006] 狼抓兔子题解

题目链接：P4001 [ICPC-Beijing 2006] 狼抓兔子

题意：

现在小朋友们最喜欢的”喜羊羊与灰太狼”。话说灰太狼抓羊不到，但抓兔子还是比较在行的，而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：

左上角点为 $(1,1)$，右下角点为 $(N,M)$（上图中 $N=3$，$M=4$）。有以下三种类型的道路：

$(x,y)\rightleftharpoons(x+1,y)$

$(x,y)\rightleftharpoons(x,y+1)$

$(x,y)\rightleftharpoons(x+1,y+1)$

道路上的权值表示这条路上最多能够通过的兔子数，道路是无向的。左上角和右下角为兔子的两个窝，开始时所有的兔子都聚集在左上角 $(1,1)$ 的窝里，现在它们要跑到右下角 $(N,M)$ 的窝中去，狼王开始伏击这些兔子。当然为了保险起见，如果一条道路上最多通过的兔子数为 $K$，狼王需要安排同样数量的 $K$ 只狼，才能完全封锁这条道路，你需要帮助狼王安排一个伏击方案，使得在将兔子一网打尽的前提下，参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦。

输入格式：

第一行两个整数 $N,M$，表示网格的大小。

接下来分三部分。

第一部分共 $N$ 行，每行 $M-1$ 个数，表示横向道路的权值。

第二部分共 $N-1$ 行，每行 $M$ 个数，表示纵向道路的权值。

第三部分共 $N-1$ 行，每行 $M-1$ 个数，表示斜向道路的权值。

输出格式：

输出一个整数，表示参与伏击的狼的最小数量。

数据范围：

保证 $3 \leq N,M \leq 1000$，所有道路的权值均为不超过 $10^6$ 的正整数。

本题正解不是网络流，而是对偶图最短路。

下图就是样例的对偶图，其中绿色的点和 $s,t$ 称为对偶图，点之间的边权就是横跨的那条边的边权。

可以证明，对偶图的最短路就是原图的最小割。

时间复杂度 $\mathcal{O}(nm \log nm)$

代码：（需要仔细想想）

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define INF 0x3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e3 + 15))

int n, m, pos = 1, head[N][N], d[N][N]; char vis[N][N];
struct Edge { int v1, v2, w, next; } e[N * N * 2 * 2];
void addEdge(int u1, int u2, int v1, int v2, int w) {
    e[++pos] = {v1, v2, w, head[u1][u2]}; head[u1][u2] = pos;
}
struct node { int u1, u2, dis; } ;
bool operator<(node a, node b) { return a.dis > b.dis; }
priority_queue<node> q;
void Dijkstra(int s1, int s2)
{
    memset(d, 0x3f, sizeof(d)); d[s1][s2] = 0; 
    for(q.push({s1, s2, 0}); !q.empty(); )
    {
        auto [u1, u2, _] = q.top(); q.pop();
        if(vis[u1][u2]) continue; else vis[u1][u2] = true;
        for(int i = head[u1][u2]; i; i = e[i].next)
        {
            int v1 = e[i].v1, v2 = e[i].v2, w = e[i].w;
            if(d[v1][v2] > d[u1][u2] + w)
            {
                d[v1][v2] = d[u1][u2] + w;
                if(!vis[v1][v2]) q.push({v1, v2, d[v1][v2]});
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    if(n == 1)
    {
        int res = INF;
        for(int i = 1, x; i < m; i++) { cin >> x; down(res, x); }
        cout << res << '\n'; return 0;
    }
    if(m == 1)
    {
        int res = INF;
        for(int i = 1, x; i < n; i++) { cin >> x; down(res, x); }
        cout << res << '\n'; return 0;
    }
    for(int i = 1, w; i <= n; i++)
        for(int j = 1; j < m; j++)
        {
            cin >> w;
            if(i == 1) {
                addEdge(i, j * 2, n + 1, m + 1, w);
                addEdge(n + 1, m + 1, i, j * 2, w);
            }else if(i == n) {
                addEdge(i - 1, j * 2 - 1, n, m, w);
                addEdge(n, m, i - 1, j * 2 - 1, w);
            }else {
                addEdge(i - 1, j * 2 - 1, i, j * 2, w);
                addEdge(i, j * 2, i - 1, j * 2 - 1, w);
            }
        }
    for(int i = 1, w; i < n; i++)
        for(int j = 1; j <= m; j++)
        {
            cin >> w;
            if(j == 1) {
                addEdge(n, m, i, j * 2 - 1, w);
                addEdge(i, j * 2 - 1, n, m, w);
            }else if(j == m) {
                addEdge(n + 1, m + 1, i, (m - 1) * 2, w);
                addEdge(i, (m - 1) * 2, n + 1, m + 1, w);
            }else {
                addEdge(i, (j - 1) * 2, i, (j - 1) * 2 + 1, w);
                addEdge(i, (j - 1) * 2 + 1, i, (j - 1) * 2, w);
            }
        }
    for(int i = 1, w; i < n; i++)
        for(int j = 1; j < m; j++)
        {
            cin >> w;
            addEdge(i, j * 2 - 1, i, j * 2, w);
            addEdge(i, j * 2, i, j * 2 - 1, w);
        }
    Dijkstra(n, m); cout << d[n + 1][m + 1] << '\n'; // 起点 (n,m) 终点 (n + 1, m + 1)
    return 0;
}