「NOI2010」海拔-网络流/最短路

题面请点击查看全文

$\text{YT}$ 市是一个规划良好的城市，城市被东西向和南北向的主干道划分为 $n\times n$ 个区域。简单起见，可以将 $\text{YT}$ 市看作一个正方形，每一个区域也可看作一个正方形。从而，$YT$ 城市中包括 $(n+1) \times (n+1)$ 个交叉路口和 $2n \times (n+1)$ 条双向道路（简称道路），每条双向道路连接主干道上两个相邻的交叉路口。

小 $\text{Z}$ 作为该市的市长，他根据统计信息得到了每天上班高峰期间 $\text{YT}$ 市每条道路两个方向的人流量，即在高峰期间沿着该方向通过这条道路的人数。每一个交叉路口都有不同的海拔高度值， $\text{YT}$ 市市民认为爬坡是一件非常累的事情，每向上爬 $h$ 的高度，就需要消耗 $h$ 的体力。如果是下坡的话，则不需要耗费体力。因此如果一段道路的终点海拔减去起点海拔的值为 $h$ (注意 $h$ 可能是负数)，那么一个人经过这段路所消耗的体力是 $\max(0, h)$ 。

小 $\text{Z}$ 还测量得到这个城市西北角的交叉路口海拔为 $0$ ，东南角的交叉路口海拔为 $1$ ，但其它交叉路口的海拔高度都无法得知。小 $\text{Z}$ 想知道在最理想的情况下（即你可以任意假设其他路口的海拔高度），每天上班高峰期间所有人爬坡消耗的总体力和的最小值。

链接

Luogu P2046

题解

可以发现，应该所有点的海拔都要么是 $0$ ，要么是 $1$ ，可以取到最优解。而且分界线应该是一条连续的线，让我们联想到最小割。

但是这个数据范围太大了，直接跑最大流会超时，所以我们将这个图转化成对偶图，根据切割方向选择边的长度，然后跑最短路即可。注意不能用 $\text{SPFA}$ 。

代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;

const int MAXN = 300000,MAXM = 2400000;
const int N = 510;

struct Edge{
    int from,to;
    ll len;int nex;
}edge[MAXM];

int n,m,s,t;
int fir[MAXN],ecnt = 2;
int a[N][N],b[N][N],c[N][N],d[N][N];


void addedge(int a,int b,int c){s
    edge[ecnt] = (Edge){a,b,c,fir[a]};
    fir[a] = ecnt++;
}

struct Point{
    int x;ll d;
    bool operator <(const Point &a)const{
        return d > a.d;
    }
};

ll dis[MAXN];
bool vis[MAXN];
priority_queue<Point> q;

void dij(){
    for(int i = 1;i<=n*n+2;i++) dis[i] = 2147483647;
    dis[s] = 0;
    q.push((Point){s,0});
    while(!q.empty()){
        Point now = q.top();q.pop();
        int nown = now.x,nowd = dis[nown];
        if(vis[nown]) continue;
        vis[nown] = 1;
        for(int nowe = fir[nown];nowe;nowe = edge[nowe].nex){
            int v = edge[nowe].to,l = edge[nowe].len;
            if(dis[v] > nowd + l){
                dis[v] = nowd + l;
                q.push((Point){v,dis[v]});
            }
        }
    }
}


int _hash(int i,int j){
    if(i <= 0 || j > n) return s;
    if(j <= 0 || i > n) return t;
    return (i-1)*n+j;
}

void init(){
    scanf("%d",&n);n++;
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n-1;j++)
            scanf("%d",&a[i][j]);
    for(int i = 1;i<=n-1;i++)
        for(int j = 1;j<=n;j++)
            scanf("%d",&b[i][j]);
    for(int i = 1;i<=n;i++)
        for(int j = 2;j<=n;j++)
            scanf("%d",&c[i][j]);
    for(int i = 2;i<=n;i++)
        for(int j = 1;j<=n;j++)
            scanf("%d",&d[i][j]);
    n--;
}

void solve(){
    s = n*n+1,t = n*n+2;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
 			addedge(_hash(i,j),_hash(i+1,j),a[i+1][j]);
 			addedge(_hash(i,j),_hash(i,j+1),d[i+1][j+1]);
 			addedge(_hash(i,j),_hash(i-1,j),c[i][j+1]);
 			addedge(_hash(i,j),_hash(i,j-1),b[i][j]);
        }
    }
    for(int i = 1;i<=n;i++){
        addedge(s,_hash(1,i),a[1][i]);
        addedge(s,_hash(i,n),b[i][n+1]);
        //addedge(,s,),addedge(,s,);
    }
    for(int i = 1;i<=n;i++){
        addedge(_hash(i,1),t,b[i][1]);
        addedge(_hash(n,i),t,a[n+1][i]);
        //addedge(t,,),addedge(t,,);
    }
    dij();
    printf("%lld\n",dis[t]);
}

signed main(){
    init();
    solve();
    return 0;
}

「NOI2010」海拔-网络流/最短路

链接

题解

代码

See Also

Comments