[BZOJ2007/Luogu2046][Noi2010]海拔(网络流,平面图对偶图,最短路)

发布于 2018-02-25  85 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2007/Luogu2046][Noi2010]海拔(网络流,平面图对偶图,最短路)

Description

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

Http

BZOJ
Luogu

Tag

网络流,平面图对偶图,最短路

解决思路

不要被题目输出要求什么四舍五入吓到了,看到左上角海拔为\(0\),右下角海拔为\(1\),那么可以贪心地猜想,图中每一个点的海拔分别是\(0\)或者是\(1\),并且\(0\)和\(1\)一定是连成一块的。那么也就是说,贡献答案的部分就是\(0\)和\(1\)交界的地方。问题转化为最小割问题。
由于数据范围较大,不能直接用网络流解决,那么考虑到这个图是平面图,所以可以转成对偶图来求最短路。
转成最短路需要注意的是,由于原平面图中正反两个方向的边的容量是不一样的,所以在对偶图中正反边的权值也是不一样的。那么为了保证顺序不变,这里选择的建图方向是,原来西到东和北到南的边在对偶图中从源点方向指向汇点方向,而原来东到西和南到北的边则在对偶图中由汇点方向指向源点方向。这样求最短路即为原图的最小割。
这里用\(Dijkstra\)实现最短路。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxMap=501;
const int maxN=maxMap*maxMap;
const int maxM=maxN*10;
const int inf=2147483647;

class Edge
{
public:
    int v;
    ll w;
};

class Queue_Data
{
public:
    int u;
    ll w;
};

bool operator < (Queue_Data A,Queue_Data B)
{
    return A.w>B.w;
}

int n,S,T;
int edgecnt=0,Head[maxN],Next[maxM],Id[maxMap][maxMap];
Edge E[maxM];
ll Dist[maxN];
priority_queue<Queue_Data> Q;
bool vis[maxN];

void Add_Edge(int u,int v,ll w);

int main()
{
    mem(Head,-1);
    ios::sync_with_stdio(false);
    cin>>n;
    int idcnt=0;
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) Id[i][j]=++idcnt;//为了方便后续操作,这里对于对偶图的每一个点先标号
    S=n*n+1;T=S+1;n++;//得到源点汇点编号
    for (int i=1;i<=n;i++)//四个矩阵分别读入四个方向的边,同时在对偶图中建图
        for (int j=1;j<n;j++)
        {
            ll w;cin>>w;
            if (i==1) Add_Edge(Id[i][j],T,w);
            else if (i==n) Add_Edge(S,Id[i-1][j],w);
            else Add_Edge(Id[i][j],Id[i-1][j],w);
        }
    for (int i=1;i<n;i++)
        for (int j=1;j<=n;j++)
        {
            ll w;cin>>w;
            if (j==1) Add_Edge(S,Id[i][j],w);
            else if (j==n) Add_Edge(Id[i][j-1],T,w);
            else Add_Edge(Id[i][j-1],Id[i][j],w);
        }
    for (int i=1;i<=n;i++)
        for (int j=1;j<n;j++)
        {
            ll w;cin>>w;
            if (i==1) Add_Edge(T,Id[i][j],w);
            else if (i==n) Add_Edge(Id[i-1][j],S,w);
            else Add_Edge(Id[i-1][j],Id[i][j],w);
        }
    for (int i=1;i<n;i++)
        for (int j=1;j<=n;j++)
        {
            ll w;cin>>w;
            if (j==1) Add_Edge(Id[i][j],S,w);
            else if (j==n) Add_Edge(T,Id[i][j-1],w);
            else Add_Edge(Id[i][j],Id[i][j-1],w);
        }
    mem(Dist,-1);Dist[S]=0;//从源点开始求最短路
    Q.push((Queue_Data){S,0});
    do
    {
        Queue_Data u=Q.top();Q.pop();
        if (vis[u.u]) continue;
        vis[u.u]=1;
        for (int i=Head[u.u];i!=-1;i=Next[i])
            if ((vis[E[i].v]==0)&&((Dist[E[i].v]==-1)||(Dist[E[i].v]>Dist[u.u]+E[i].w)))
            {
                Dist[E[i].v]=Dist[u.u]+E[i].w;
                Q.push((Queue_Data){E[i].v,Dist[E[i].v]});
            }
    }
    while (!Q.empty());
    printf("%lld\n",Dist[T]);
    return 0;
}

void Add_Edge(int u,int v,ll w)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;
    E[edgecnt].v=v;E[edgecnt].w=w;
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2007/Luogu2046][Noi2010]海拔(网络流,平面图对偶图,最短路)


HNCJ OIer