B20J_2007_[Noi2010]海拔_平面图最小割转对偶图+堆优化Dij

题意：城市被东西向和南北向的主干道划分为n×n个区域。城市中包括(n+1)×(n+1)个交叉路口和2n×(n+1)条双向道路，已知每天每条道路两个方向的人流量，即沿着该方向通过这条道路的人数。每一个交叉路口都有不同的海拔高度值，每向上爬h的高度，就需要消耗h的体力。如果是下坡的话，则不需要耗费体力。已知城市西北角的交叉路口海拔为0，东南角的交叉路口海拔为1(如上图所示)，但其它交叉路口的海拔高度都无法得知。小Z想知道在最理想的情况下（即你可以任意假设其他路口的海拔高度），每天上班高峰期间所有人爬坡所消耗的总体力和的最小值。结果四舍五入到整数。

分析：因为城市的每个点之间都是连续的，所以不考虑0到1中的小数。

直接将地图分成海拔为0，1的两部分并不会使答案更差。此题就转化为求最小割。

然而边数有近百万，直接用dinic会炸掉。考虑转化成对偶图。

把从西向东的边看成从上到下，源点连最上最右两行。其他边同理。

连好边跑最短路，看边的数量选择堆优化Dij

代码

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <queue>

#define S (n*n+1)

#define T (n*n+2)

#define p(x,y) (n*(x-1)+y)

using namespace std;

priority_queue <pair <int,int> >q;

int head[300020],to[1500010],nxt[1500010],val[1500010],cnt,n;

int dis[300020],vis[300020];

inline void add(int u,int v,int w)

{

    to[++cnt]=v;

    nxt[cnt]=head[u];

    head[u]=cnt;

    val[cnt]=w;

}

inline void read(int &x)

{

    int f=1;x=0;char s=getchar();

    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}

    while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();}

    x*=f;

}

int main()

{

    read(n);

    int x;

    register int i,j;

    for(i=0;i<=n;++i)

    {

        for(j=1;j<=n;++j)

        {

            read(x);

            if(i==0)add(S,p(1,j),x);

            else if(i==n)add(p(n,j),T,x);

            else add(p(i,j),p(i+1,j),x);

        }

    }

    for(i=1;i<=n;++i)

    {

        for(j=0;j<=n;++j)

        {

            read(x);

            if(j==0)add(p(i,1),T,x);

            else if(j==n)add(S,p(i,n),x);

            else add(p(i,j+1),p(i,j),x);

        }

    }

    for(i=0;i<=n;++i)

    {

        for(j=1;j<=n;++j)

        {

            read(x);

            if(i==0)add(p(1,j),S,x);

            else if(i==n)add(T,p(n,j),x);

            else add(p(i+1,j),p(i,j),x);

        }

    }

    for(i=1;i<=n;++i)

    {

        for(j=0;j<=n;++j)

        {

            read(x);

            if(j==0)add(T,p(i,1),x);

            else if(j==n)add(p(i,n),S,x);

            else add(p(i,j),p(i,j+1),x);

        }

    }

    for(i=0;i<=T;++i)

        dis[i]=100000000;

    dis[S]=0;

    q.push(make_pair(-dis[S],S));

    while(q.size())

    {

        int x=q.top().second;

        q.pop();

        if(vis[x])continue;

        vis[x]=1;

        for(i=head[x];i;i=nxt[i])

        {

            if(dis[to[i]]>dis[x]+val[i])

            {

                dis[to[i]]=dis[x]+val[i];

                q.push(make_pair(-dis[to[i]],to[i]));

            }

        }

    }

    printf("%d\n",dis[T]);

}

/***************************************************************

    Problem: 1897

    User: 20170105

    Language: C++

    Result: Accepted

    Time:584 ms

    Memory:22164 kb

****************************************************************/

巴特西

B20J_2007_[Noi2010]海拔_平面图最小割转对偶图+堆优化Dij

最新文章

热门文章