題目描述

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想知道在最理想的情況下（即你可以任意假設其他路口的海拔高度），每天上班高峰期間所有人爬坡消耗的總體力和的最小值。

輸入輸出格式

輸入格式：

?

第一行包含一個整數n，含義如上文所示。

接下來4n(n + 1)行，每行包含一個非負整數分別表示每一條道路每一個方向的人流量信息。輸入順序：n(n + 1)個數表示所有從西到東方向的人流量，然后n(n + 1)個數表示所有從北到南方向的人流量，n(n + 1)個數表示所有從東到西方向的人流量，最后是n(n + 1)個數表示所有從南到北方向的人流量。對于每一個方向，輸入順序按照起點由北向南，若南北方向相同時由西到東的順序給出(參見樣例輸入)。

?

輸出格式：

?

僅包含一個數，表示在最理想情況下每天上班高峰期間所有人爬坡所消耗的總體力和（即總體力和的最小值），結果四舍五入到整數。

?

輸入輸出樣例

輸入樣例#1：
1 1 2 3 4 5 6 7 8 輸出樣例#1：
3

說明

對于20%的數據：n ≤ 3；

對于50%的數據：n ≤ 15；

對于80%的數據：n ≤ 40；

對于100%的數據：1 ≤ n ≤ 500，0 ≤ 流量 ≤ 1,000,000且所有流量均為整數。

吐槽

　　吐槽惡心的輸入……

　　BZOJ所有點一起評測，算總時間，我寫spfa跑了8000+ms，交到洛谷上就TLE了兩個點，給spfa加了SLF優化，依然只能8個點，再去大牛分站開O2，過了9個點。假設BZOJ和洛谷給我評測的那臺評測機速度一樣，洛谷#1到#9我總共跑了1500ms左右，那么#10我的要跑6000ms+啊，害怕……

　　spfa的LLL優化寫這題得不償失，代碼長了容易錯，反正也沒負邊權，就寫了dijkstra，我用了最裸的堆優化，在洛谷主站(無O2)跑了1137ms，當時洛谷rank24，再去大牛分站開O2跑一波，409ms，正好rank10，看了看rank1的200+ms，那位dalao用的是algorithm里的heap，好像這玩意跑得比手寫二叉堆還快，過幾天學一下，不知道可不可以像pb_ds中的配對對一樣無腦替代priority_queue。雖然平板電視里的配對堆快得多，但我嫌pb_ds使用方法過于復雜，單詞太難背了……

解題思路

　　像BZOJ 1001狼爪兔子一樣，本來是求原圖最大流，但數據范圍過大，會被卡。由于兩題的圖都是平面圖，所以可以建對偶圖，然后在對偶圖上跑最短路(最小割)

源代碼

1、spfa加SLF優化//不加這個優化在BZOJ、cogs上都能過了

#include<queue> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;int n;struct Edge{int next,to,w; }e[2000010]; int cnt=1,head[2000010]={0}; void add(int u,int v,int w) {e[cnt]={head[u],v,w};head[u]=cnt++; } int s,t; int dis[2000010]; bool inq[2000010]={0}; int spfa() {memset(dis,0x7f,sizeof(dis));queue<int> q;dis[s]=0;inq[s]=1;q.push(s);while(!q.empty()){int u=q.front();q.pop();inq[u]=0;for(int i=head[u];i;i=e[i].next){int v=e[i].to,w=e[i].w;if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;if(!inq[v]){q.push(v);inq[v]=1;}}}}return dis[t]; }int main() {//freopen("altitude.in","r",stdin);//freopen("altitude.out","w",stdout);scanf("%d",&n);s=n*n+1,t=n*n+2;/***從左到右***/for(int i=0,w;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&w);if(i==0)add(s,(j-1)*n+1,w);else if(i==n)add(j*n,t,w);elseadd((j-1)*n+i,(j-1)*n+i+1,w);}}/******//***從上到下***/for(int i=1,w;i<=n;i++){for(int j=0;j<=n;j++){scanf("%d",&w);if(j==0)add(i,t,w);else if(j==n)add(s,i+n*(n-1),w);elseadd(j*n+i,(j-1)*n+i,w);}}/******//***從右向左***/for(int i=0,w;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&w);if(i==0)add((j-1)*n+1,s,w);else if(i==n)add(t,j*n,w);elseadd((j-1)*n+i+1,(j-1)*n+i,w);}}/******//***從下到上***/for(int i=1,w;i<=n;i++){for(int j=0;j<=n;j++){scanf("%d",&w);if(j==0)add(t,i,w);else if(j==n)add(i+n*(n-1),s,w);elseadd((j-1)*n+i,j*n+i,w);}}/******//*for(int i=1;i<=n*n+2;i++){for(int j=head[i];j;j=e[j].next)printf("%d=>%d %d\n",i,e[j].to,e[j].w);}*///輸出建好的圖/***沒啦***/printf("%d\n",spfa());return 0; }

?

2、堆優化的dijkstra

#include<queue> #include<cstdio> #include<cstring> #include<algorithm>int n;struct Edge{int next,to,w; }e[2000010]; int cnt=1,head[2000010]={0}; void add(int u,int v,int w) {e[cnt]={head[u],v,w};head[u]=cnt++; } int s,t; int dis[2000010]; bool vis[2000010]={0}; struct P{int u,D;bool operator < (const P & a)const{return D>a.D;} }temp; int dijkstra() {memset(dis,0x7f,sizeof(dis));dis[s]=0;std::priority_queue<P> q;q.push({s,0});while(!q.empty()){temp=q.top();q.pop();int u=temp.u,D=temp.D;if(vis[u]) continue;vis[u]=1;for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(dis[v]>D+e[i].w){dis[v]=D+e[i].w;q.push({v,dis[v]});}}}return dis[t]; }int main() {//freopen("altitude.in","r",stdin);//freopen("altitude.out","w",stdout);scanf("%d",&n);s=n*n+1,t=n*n+2;/***從左到右***/for(int i=0,w;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&w);if(i==0)add(s,(j-1)*n+1,w);else if(i==n)add(j*n,t,w);elseadd((j-1)*n+i,(j-1)*n+i+1,w);}}/******//***從上到下***/for(int i=1,w;i<=n;i++){for(int j=0;j<=n;j++){scanf("%d",&w);if(j==0)add(i,t,w);else if(j==n)add(s,i+n*(n-1),w);elseadd(j*n+i,(j-1)*n+i,w);}}/******//***從右向左***/for(int i=0,w;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&w);if(i==0)add((j-1)*n+1,s,w);else if(i==n)add(t,j*n,w);elseadd((j-1)*n+i+1,(j-1)*n+i,w);}}/******//***從下到上***/for(int i=1,w;i<=n;i++){for(int j=0;j<=n;j++){scanf("%d",&w);if(j==0)add(t,i,w);else if(j==n)add(i+n*(n-1),s,w);elseadd((j-1)*n+i,j*n+i,w);}}/******//*for(int i=1;i<=n*n+2;i++){for(int j=head[i];j;j=e[j].next)printf("%d=>%d %d\n",i,e[j].to,e[j].w);}*///輸出建好的圖/***沒啦***/printf("%d\n",dijkstra());return 0; }

?

轉載于:https://www.cnblogs.com/wawcac-blog/p/7065776.html

總結

以上是生活随笔為你收集整理的洛谷 P2046 BZOJ 2007 海拔(NOI2010)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。