[NOI2010]海拔


题目链接:Luogu2046
Time Limit:2000ms / Memory Limit:256MB


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想知道在最理想的情况下(即你可以任意假设其他路口的海拔高度),每天上班高峰期间所有人爬坡消耗的总体力和的最小值。


Input
第一行包含一个整数n,含义如上文所示。

接下来4n(n+1)行,每行包含一个非负整数分别表示每一条道路每一个方向的人流量信息。输入顺序:n(n+1)个数表示所有从西到东方向的人流量,然后n(n+1)个数表示所有从北到南方向的人流量,n(n+1)个数表示所有从东到西方向的人流量,最后是n(n+1)个数表示所有从南到北方向的人流量。对于每一个方向,输入顺序按照起点由北向南,若南北方向相同时由西到东的顺序给出(参见样例输入)。


Output
仅包含一个数,表示在最理想情况下每天上班高峰期间所有人爬坡所消耗的总体力和(即总体力和的最小值),结果四舍五入到整数。


Sample Input 1
1
1
2
3
4
5
6
7
8


Sample Output 1
3


Hint

对于20%的数据:n≤3;
对于50%的数据:n≤15;
对于80%的数据:n≤40;
对于100%的数据:1≤n≤500,0≤流量≤1,000,000且所有流量均为整数。


Solution
练平面图转对偶图写的题
把平面图转成对偶图跑遍最短路就OK


如何建对偶图?
具体的建图过程可以点开下面这个链接qwq
平面图转对偶图


Code

#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
//#define Judge
//#define Online
#define reg register
#define ll long long
#define mod 1000000007
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
using namespace std;
#ifdef Judge
#define puts io.put
#define getchar io.gc
#define putchar io.wchar
#ifdef Online
FILE*in=stdin;
FILE*out=stdout;
#else
FILE*in=fopen(".in","r+");
FILE*out=fopen(".out","w+");
#endif
struct FastIO{
    #define S 1000000
    int wpos,len,pos;char wbuf[S],buf[S];
    FastIO(){wpos=0,len=0,pos=0;}
    inline char gc(){
        if (pos==len) pos=0,len=fread(buf,1,S,in);
        if (pos==len) return 0; return buf[pos++];
    }
    inline void wchar(int x) {
        if (wpos==S) fwrite(wbuf,1,S,out),wpos=0;
        wbuf[wpos++]=x;
    }
    inline void put(const char*s) {for(; *s; ) wchar(*s++);}
    ~FastIO() {
        if (wpos) fwrite(wbuf,1,wpos,out),wpos=0;
    }
}io;
#endif
template<typename T> inline void read(T&x){T f=1;x=0;char c;
    for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
    for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
    int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
#define maxn 600
#define maxm 10100000
int n,m,S,T;
int fir[maxn*maxn],nxt[maxm],to[maxm],flow[maxm],dis[maxm],cnt;
inline void ins(int x,int y,int v){
    nxt[++cnt]=fir[x],fir[x]=cnt,to[cnt]=y,flow[cnt]=v;
}
struct operator_node{
    inline int operator()(int&x,int&y)const{
        return dis[x]>dis[y];
    }
};
inline void Dijkstra(){
    priority_queue<int,vector<int>,operator_node> que;
    memset(dis,127,sizeof dis);dis[S]=0,que.push(S);
    while(!que.empty()){
        int now=que.top();que.pop();
        for (int i=fir[now]; i; i=nxt[i])
            if (dis[now]+flow[i]<dis[to[i]]) dis[to[i]]=dis[now]+flow[i],que.push(to[i]);
    }
}
/*inline void Init(){
    m=n*(n+1);S=1,T=n*n+2;
    for (int i=0; i<=m; i+=n+1){
        for (int j=i,g=i+n; j<g; ++j){
            int v;read(v);ins(j,j+1,v);
            cerr<<j<<' '<<j+1<<' '<<v<<'\n';
        }
        // cerr<<i+n<<'\n';
    }
    for (int i=0; i<=n; ++i){
        for (int j=i,g=m; j<g; j+=n+1){
            int v;read(v);ins(j,j+n+1,v);
            cerr<<j<<' '<<j+n+1<<' '<<v<<'\n';
        }
    }
    for (int i=0; i<=m; i+=n+1){
        for (int j=i,g=i+n; j<g; ++j){
            int v;read(v);ins(j+1,j,v);
            cerr<<j+1<<' '<<j<<' '<<v<<'\n';
        }
    }
    for (int i=0; i<=n; ++i){
        for (int j=i,g=m; j<g; j+=n+1){
            int v;read(v);ins(j+n+1,j,v);
            cerr<<j+n+1<<' '<<j<<' '<<v<<'\n';
        }
    }
}*/
inline void Init(){
    T=n*n+2;
    for (int i=0; i<=n; ++i){
        for (int j=1; j<=n; ++j){
            int x; read(x);
            if (i==0) ins(j+1,T,x);
            else if (i==n) ins(S,(i-1)*n+j+1,x);
            else ins(i*n+j+1,(i-1)*n+j+1,x);
        }
    }
    for (int i=1; i<=n; ++i){
        for (int j=0; j<=n; ++j){
            int x; read(x);
            if (j==0) ins(S,(i-1)*n+2,x);
            else if (j==n) ins(i*n+1,T,x);
            else ins((i-1)*n+j+1,(i-1)*n+j+2,x);
        }
    }
    for (int i=0; i<=n; ++i){
        for (int j=1; j<=n; ++j){
            int x; read(x);
            if (i==0) ins(T,j+1,x);
            else if (i==n) ins((i-1)*n+j+1,S,x);
            else ins((i-1)*n+j+1,i*n+j+1,x);
        }
    }
    for (int i=1; i<=n; ++i){
        for (int j=0; j<=n; ++j){
            int x; read(x);
            if (j==0) ins((i-1)*n+2,S,x);
            else if (j==n) ins(T,i*n+1,x);
            else ins((i-1)*n+j+2,(i-1)*n+j+1,x);
        }
    }
}
int main(int argv,char*argc[]){
    read(n);Init();Dijkstra();wt(dis[T],'\n');
    return 0;
}


点我回到主页

One thought on “[NOI2010]海拔

  1. Pingback引用通告: 平面图转对偶图 – TaK-Vin

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google photo

You are commenting using your Google account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s