NOI2010 海拔

题目:

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

思路:

  从贪心的角度分析会发现,所有点的高度都在 之间,而且一个点 西北方向的点一定不比 矮,东南方向的点一定不比 高(因为不可能出现先走上坡再走下坡的情况)。而所有高度是小数的情况都能找到相同的价值的整数解。
  所以问题就变成了把所有点划分成 两个点集,也就是西北角和东南角的最小割。因为是网格图,可以转化成最短路求解。有向图就只要注意一下方向即可(考虑一下穿过去的时候哪边是 哪边是 就能很简单的分析了)。

代码:

#include <bits/stdc++.h>
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
#define ALL(x) x.begin(), x.end() 
#define mset(a, b) memset(a, b, sizeof a) 
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int N = 300100, M = 4 * N;

template<int N, int M, class T> struct Link {
#define erep(k, G, o) for(int k(G.HEAD[o]); k; k = G.NXT[k])
    int HEAD[N], NXT[M], tot; T W[M];
    void add(int x, T w) {NXT[++tot] = HEAD[x]; W[HEAD[x] = tot] = w;}
    T& operator[] (int x) {return W[x];}
};

struct Edge {
    int to, w;
};
Link<N, M, Edge> G;

int n, s, t;
int id(int x, int y) {
    if(x < 1 || y > n) return s;
    if(x > n || y < 1) return t;
    return y + (x - 1) * n;
}

struct Data {
    int id, val;
    bool operator< (const Data d) const {
        return val > d.val;
    }
};

priority_queue<Data> hp;
int dis[N];
int dij(int s, int t) {
    mset(dis, 63); dis[s] = 0;
    hp.push((Data) {s, 0});
    while(!hp.empty()) {
        Data d = hp.top(); hp.pop();
        if(dis[d.id] != d.val) continue;
        erep(k, G, d.id) {
            Edge e = G[k];
            if(tomin(dis[e.to], d.val + e.w))
                hp.push((Data) {e.to, dis[e.to]});
        }
    }
    return dis[t];
}

int main() {
    File(altitude);
    scanf("%d", &n);
    s = n * n + 2; t = n * n + 1;
    int val;
    rep(i, 1, n + 1) 
        rep(j, 1, n) {
            scanf("%d", &val);
            G.add(id(i - 1, j), (Edge) {id(i, j), val});
        }
    rep(i, 1, n) 
        rep(j, 1, n + 1) {
            scanf("%d", &val);
            G.add(id(i, j), (Edge) {id(i, j - 1), val});
        }
    rep(i, 1, n + 1) 
        rep(j, 1, n) {
            scanf("%d", &val);
            G.add(id(i, j), (Edge) {id(i - 1, j), val});
        }
    rep(i, 1, n)
        rep(j, 1, n + 1) {
            scanf("%d", &val);
            G.add(id(i, j - 1), (Edge) {id(i, j), val});
        }
    printf("%d\n", dij(s, t));
    return 0;
}