Problem Specification Value
Time Limit 15 Sec
Memory Limit 162 MB
Submit 17131
Solved 4191

Description

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

左上角点为 (1, 1), 右下角点为 (N, M) (上图中 N=4, M=5). 有以下三种类型的道路

  1. (x, y) <==> (x+1, y)
  2. (x, y) <==> (x, y+1)
  3. (x, y) <==> (x+1, y+1)

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

Input

第一行为 N, M. 表示网格的大小, N, M 均小于等于 1000.

接下来分三部分

  • 第一部分共 N 行, 每行 M-1 个数, 表示横向道路的权值.
  • 第二部分共 N-1 行, 每行 M 个数, 表示纵向道路的权值.
  • 第三部分共 N-1 行, 每行 M-1 个数, 表示斜向道路的权值.

输入文件保证不超过 10M

Output

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

Sample Input

3 4
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6

Sample Output

14

HINT

2015. 4. 16 新加数据一组, 可能会卡掉从前可以过的程序.

Source

实质上是一道网络流题, 同时具有最小割的性质. 我们也可以用最短路来做这道题 (也就是对偶图). 这一条最短路代表了一个规则图形从左下到右上的过程. 其实是很明显的. 但是我并未能用 Dinic AC 这道题~

最后用的 SPFA 水过, 内存 121MB~

说一句题外话: 我为了这道题专门编了一个对拍用的 Python 框架, 就叫 pyDataGen.

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;
const int maxn = 2000100, maxm = 6000100;
const long long infinit = 0x0f3f3f3f3f3f3f3fll;

class Spfa
{
public:
    struct edge
    {
        int v;
        long long len;
        edge *next;
    };
    edge *edges[maxn], epool[maxm];
    int n, s, t, cnt, inque[maxn];
    long long dist[maxn];
    void addedge(int u, int v, long long len)
    {
        edge *p = &epool[cnt++], *q = &epool[cnt++];
        p->v = v; p->len = len; p->next = edges[u]; edges[u] = p;
        q->v = u; q->len = len; q->next = edges[v]; edges[v] = q;
        return ;
    }
    void spfa(void)
    {
        queue<int> que;
        memset(inque, 0, sizeof(inque));
        for (int i = 1; i <= n; i++) dist[i] = infinit;
        que.push(s); dist[s] = 0; inque[s] = 1;
        while (!que.empty()) {
            int p = que.front(); que.pop(); inque[p] = 0;
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (dist[ep->v] > dist[p] + ep->len) {
                    dist[ep->v] = dist[p] + ep->len;
                    if (!inque[ep->v]) {
                        que.push(ep->v);
                        inque[ep->v] = 1;
                    }
                }
        }
        return ;
    }
} graph;

int n, m;
long long res = 0;

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    if (n > 1 && m > 1) {
        graph.n = 2 * (n - 1) * (m - 1) + 2;
        graph.s = graph.n - 1;
        for (int i = 1; i <= n; i++)
            for (int j = 1, k; j < m; j++) {
                scanf("%d", &k);
                if (i == 1) graph.addedge((2 * i - 2) * (m - 1) + j, graph.n, k);
                else if (i == n) graph.addedge(graph.n - 1, (2 * i - 3) * (m - 1) + j, k);
                else graph.addedge((2 * i - 2) * (m - 1) + j, (2 * i - 3) * (m - 1) + j, k);
            }
        for (int i = 1; i < n; i++)
            for (int j = 1, k; j <= m; j++) {
                scanf("%d", &k);
                if (j == 1) graph.addedge(graph.n - 1, (2 * i - 1) * (m - 1) + j, k);
                else if (j == m) graph.addedge((2 * i - 2) * (m - 1) + j - 1, graph.n, k);
                else graph.addedge((2 * i - 1) * (m - 1) + j, (2 * i - 2) * (m - 1) + j - 1, k);
            }
        for (int i = 1; i < n; i++)
            for (int j = 1, k; j < m; j++) {
                scanf("%d", &k);
                graph.addedge((2 * i - 1) * (m - 1) + j, (2 * i - 2) * (m - 1) + j, k);
            }
        graph.spfa();
        res = graph.dist[graph.n];
    } else if (n == 1 && m == 1) {
        res = 0;
    } else {
        res = infinit;
        for (int i = 1, k; i <= max(n, m); i++) {
            scanf("%d", &k);
            res = min(res, (long long)k);
        }
    }
    printf("%lld\n", res);
    return 0;
}
from pydatagen import *
n = randrange(1, 1000)
m = randrange(1, 1000)
rg = range(1, 2147483647)
printf('%d %d\n' % (n, m))
print_oi(randlist2d(n, m - 1, rg))
print_oi(randlist2d(n - 1, m, rg))
print_oi(randlist2d(n - 1, m - 1, rg))
fclose()