Description

YT 市是一个规划良好的城市, 城市被东西向和南北向的主干道划分为 \(n \times n\) 个区域. 简单起见, 可以将 YT 市看作一个正方形, 每一个区域也可看作一个正方形. 从而, YT 城市中包括 \((n+1) \times (n+1)\) 个交叉路口和 \(2n \times (n+1)\) 条双向道路 (简称道路), 每条双向道路连接主干道上两个相邻的交叉路口. 下图为一张 YT 市的地图 \((n = 2)\), 城市 被划分为 \(2 \times 2\) 个区域, 包括 \(3 \times 3\) 个交叉路口和 \(12\) 条双向道路. 小 Z 作为该市的市长, 他根据统计信息得到了每天上班高峰期间 YT 市每条道路两个方向的人流量, 即在高峰期间沿着该方向通过这条道路的人数. 每一个交叉路口都有不同的海拔高度 值, YT 市市民认为爬坡是一件非常累的事情, 每向上爬 \(h\) 的高度, 就需要消耗 \(h\) 的体力. 如果是下坡的话, 则不需要耗费体力. 因此如果一段道路的终点海拔减去起点海拔的 值为 \(h\) (注意 \(h\) 可能是负数), 那么一个人经过这段路所消耗的体力是 \(max\{0, h\}\) (这里 \(max\{a, b\}\) 表示取 \(a, b\) 两个值中的较大值). 小 Z 还测量得到这个城市西北角 的交叉路口海拔为 \(0\), 东南角的交叉路口海拔为 \(1\) (如上图所示), 但其它交叉路口的 海拔高度都无法得知. 小 Z 想知道在最理想的情况下 (即你可以任意假设其他路口的海拔高度), 每天上班高峰期间所有人爬坡所消耗的总体力和的最小值.

Input

第一行包含一个整数 \(n\), 含义如上文所示.

接下来 \(4n(n + 1)\) 行, 每行包含一个非负整数分别表示每一条道路每一个方向的人流量 信息. 输入顺序:\(n(n + 1)\) 个数表示所有从西到东方向的人流量, 然后 \(n(n + 1)\) 个数 表示所有从北到南方向的人流量,\(n(n + 1)\) 个数表示所有从东到西方向的人流量, 最后是 \(n(n + 1)\) 个数表示所有从南到北方向的人流量. 对于每一个方向, 输入顺序按照起点 由北向南, 若南北方向相同时由西到东的顺序给出 (参见样例输入).

Output

仅包含一个数, 表示在最理想情况下每天上班高峰期间所有人爬坡所消耗的总体力和 (即总 体力和的最小值), 结果四舍五入到整数.

Sample Input

1
1
2
3
4
5
6
7
8

Sample Output

3

Data Range

对于 20% 的数据:\(n \leq 3\);

对于 50% 的数据:\(n \leq 15\);

对于 80% 的数据:\(n \leq 40\);

对于 100% 的数据:\(1 \leq n \leq 500, 0 \leq 流量 \leq 10^6\) 且所有流量均为整数.

Explanation

看一眼就知道, 其实在中间设一个悬崖就可以了, 其他人都不必要多走 (即走平路). 这个 悬崖, 其实换句话说就是这张图的最小割. 怎么想到的呢, 想假设整个图都比较缓, 然后 有的地方人太多太费力气, 就把他们匀到人少的地方 (好像有点不公平). 但是既然匀了 何不把整个高度全都匀掉呢~

而且下坡路并没有什么意义, 因为还不如让别人少走一点上坡路, 反正下坡路平路都不消耗力气, 何必占那个便宜呢...... 然后最后发现只有一个割上的人需要爬高度为 \(1\) 的上坡路.

然后发现用最小割骗到了 80 分...... 如果是考场上我就直接最小割 Dinic 水过此题了...... 但是这是 BZOJ. 于是我们发现它是一个网格图, 网格图就可以直接转化成对偶图来跑一个 最短路了 (详解参见 bzoj1001 狼抓兔子=w=).

当然由于 SPFA 最坏复杂度太高 \(O(nm)\), 所以我们只能用堆优化 Dijkstra, 复杂度为 \(O((n+m) \log m)\), 换成网格图就是 \(O(2 n^2 \log n)\), 还可以凑合过去.

Source Code


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

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
using namespace std;
typedef long long lli;
const int maxn = 10001000, maxm = 10001000;
const lli infinit = 0x007f7f7f7f7f7f7fll;

class DijkstraShortestPath
{
public:
    struct edge
    {
        int u, v; lli len;
        edge* next;
    };
    int ecnt, n, s, t;
    edge *edges[maxn], epool[maxm];
    lli dist[maxn];
    bool vis[maxn];
    void add_edge(int u, int v, lli len)
    {
        edge *p = &epool[++ecnt];
        p->u = u; p->v = v; p->len = len;
        p->next = edges[u]; edges[u] = p;
        return ;
    }
    lli eval(void)
    {
        priority_queue< pair<lli, int> > que;
        for (int i = 0; i <= n; i++)
            dist[i] = infinit, vis[i] = false;
        dist[s] = 0;
        que.push(make_pair(-dist[s], s));
        while (!que.empty()) {
            int p = que.top().second;
            que.pop();
            if (vis[p])
                continue;
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (dist[p] + ep->len < dist[ep->v]) {
                    dist[ep->v] = dist[p] + ep->len;
                    que.push(make_pair(-dist[ep->v], ep->v));
                }
            vis[p] = true;
            if (p == t)
                break;
        }
        return dist[t];
    }
} graph;

int n;

int nid(int y, int x)
{
    if (x <= 0 || y >= n+1)
        return graph.s;
    else if (y <= 0 || x >= n+1)
        return graph.t;
    return (y-1) * n + x;
}

int main(int argc, char** argv)
{
    scanf("%d", &n);
    graph.n = n*n + 1;
    graph.s = 0;
    graph.t = n*n + 1;
    rep(i, 0, n) rep(j, 1, n) {
        int x = 0; scanf("%d", &x);
        graph.add_edge(nid(i+1,j), nid(i,j), x);
    }
    rep(i, 1, n) rep(j, 0, n) {
        int x = 0; scanf("%d", &x);
        graph.add_edge(nid(i,j), nid(i,j+1), x);
    }
    rep(i, 0, n) rep(j, 1, n) {
        int x = 0; scanf("%d", &x);
        graph.add_edge(nid(i,j), nid(i+1,j), x);
    }
    rep(i, 1, n) rep(j, 0, n) {
        int x = 0; scanf("%d", &x);
        graph.add_edge(nid(i,j+1), nid(i,j), x);
    }
    lli res = graph.eval();
    printf("%lld\n", res);
    return 0;
}