题解洛谷 P2046 【[NOI2010]海拔】

首先进行贪心，发现海拔有梯度时一定是不优的，最优的情况是海拔像断崖一样上升，也就是左上角有一片海拔高度为\(0\)，右下角有一片海拔高度为\(1\)。

发现这样的性质后，不难想到用最小割来解决问题，但数据规模过大，需要进行优化。

考虑到网格图是特殊的平面图，那么我们就将平面图转化为对偶图，通过对偶图求最短路来求平面图的最小割。

下面分析如何转化为对偶图：

我的做法是先\(n++\)，使\(n×n\)个区域转化为\(n×n\)个点。

一个区域用其左上角点的坐标来表示。（图中的红点）

平面图中的有向边顺时针旋转\(90°\)后作为对偶图中的边，例如当原图的有向边为自西向东（从左到右）时，连边情况应为：

黄色箭头表示原平面图中的边，蓝色箭头表示对偶图中的边，其他三种情况同理。

建完对偶图后，从\(S\)到\(T\)的最短路即为答案。

实现细节就看代码吧

\(code:\)

#include<bits/stdc++.h>

#define maxn 1200000

#define inf 2000000000

using namespace std;

template<typename T> inline void read(T &x)

{

	x=0;char c=getchar();bool flag=false;

	while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}

	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

	if(flag) x=-x;

}

int n,s,t;

struct edge

{

    int to,nxt,v;

}e[maxn];

int head[maxn],edge_cnt;

void add(int from,int to,int val)

{

    e[++edge_cnt]=(edge){to,head[from],val};

    head[from]=edge_cnt;

}

int num(int x,int y)

{

	return y+(x-1)*n;

}

struct node

{

    int val,num;

    friend bool operator <(const node &x,const node &y)

    {

        return x.val>y.val;

    }

};

priority_queue<node> q;

int dis[maxn];

bool vis[maxn];

void dijkstra()

{

    for(int i=s;i<=t;++i) dis[i]=inf;

    dis[s]=0;

    q.push((node){0,s});

    while(!q.empty())

    {

        node tmp=q.top();

        q.pop();

        int x=tmp.num;

        if(vis[x]) continue;

        vis[x]=true;

        for(int i=head[x];i;i=e[i].nxt)

        {

            int y=e[i].to,v=e[i].v;

            if(dis[y]>dis[x]+v)

            {

                dis[y]=dis[x]+v;

                q.push((node){dis[y],y});

            }

        }

    }

}

int main()

{

	read(n),n++;

    t=n*n+1;

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

    {

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

        {

            int val;

            read(val);

            if(i==1) add(s,num(i,j),val);

            else if(i==n) add(num(i-1,j),t,val);

            else add(num(i-1,j),num(i,j),val);

        }

    }

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

    {

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

        {

            int val;

            read(val);

            if(j==1) add(num(i,j),t,val);

            else if(j==n) add(s,num(i,j-1),val);

            else add(num(i,j),num(i,j-1),val);

        }

    }

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

    {

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

        {

            int val;

            read(val);

            if(i==1) add(num(i,j),s,val);

            else if(i==n) add(t,num(i-1,j),val);

            else add(num(i,j),num(i-1,j),val);

        }

    }

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

    {

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

        {

            int val;

            read(val);

            if(j==1) add(t,num(i,j),val);

            else if(j==n) add(num(i,j-1),s,val);

            else add(num(i,j-1),num(i,j),val);

        }

    }

    dijkstra();

    printf("%d",dis[t]);

	return 0;

}

巴特西

题解洛谷 P2046 【[NOI2010]海拔】

最新文章

热门文章

巴特西

题解 洛谷 P2046 【[NOI2010]海拔】

最新文章

热门文章

题解洛谷 P2046 【[NOI2010]海拔】