bzoj2007 [Noi2010]海拔

題目連結：bzoj2007

題目大意：

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

注意，海拔是可以一樣的，我以為一定要不同想了一下午！QwQ

題解：

求對偶圖轉最短路。

首先，可以知道海拔是可以一樣的。那麼我們就會想讓一樣的盡量多，于是左上角就會有一堆0，而右下角是一堆1，其實就是找個0-1的分界線。

就是直接在原圖求最小割。【如果範圍允許的話

可是對于100%的資料：1 ≤ n ≤ 500 就是有二十五萬個點。

就要學對偶圖這種東西了。。

圖檔轉自http://blog.sina.com.cn/s/blog_86942b1401014ajk.html

要轉對偶圖的一般都是像這樣的矩陣形式的吧。

學習資料：http://blog.sina.com.cn/s/blog_60707c0f01011fnn.html

設一個超級源點在附加面上，一個超級彙點在無界面。圖中的每個面或者說每個區域中都有且隻有一個點，原圖中的邊的割為對偶圖的邊，其流量就是邊長。無向圖就直接這樣建就好了。

而有向圖的話還要考慮方向。有一個好的方法就是把原圖中的邊全都順時針或全都逆時針旋轉90°，于是對偶圖中的邊的方向就是旋轉後的邊的方向。

神呐我搞了一個下午加半個晚上(加上打題解算大半個了QwQ)

為什麼呢。

1. 看錯題

• 海拔能一樣
• 盡管輸入豎邊也是先從左到右再從上到下

2.邊數組開小了！而bzoj提示我TLE啊。。于是我拿hyc的代碼改啊改= =

對拍發現數組開小了還能WA啊orz

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

struct node
{
    int x,y,c,next;
}a[maxn*8];int len,first[maxn];
void ins(int x,int y,int c)
{
    len++;a[len].x=x;a[len].y=y;a[len].c=c;
    a[len].next=first[x];first[x]=len;
}
struct nod
{
    int x,id;
    bool operator < (const nod y) const
    {
        return x>y.x;
    }
};int S,T,d[maxn];
priority_queue<nod> q;
int dijkstra()
{
    memset(d,,sizeof(d));
    nod ls;ls.id=S;ls.x=;
    d[S]=;q.push(ls);
    while (!q.empty())
    {
        nod now=q.top();q.pop();
        int x=now.id;
        if (now.x!=d[x]) continue;
        if (x==T) return d[x];
        for (int k=first[x];k!=-;k=a[k].next)
        {
            int y=a[k].y;
            if (d[y]>d[x]+a[k].c)
            {
                d[y]=d[x]+a[k].c;
                ls.id=y;ls.x=d[y];
                q.push(ls);
            }
        }
    }
    return d[T];
}
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    int n,i,j,x;
    scanf("%d",&n);
    S=n*n+;T=S+;len=;
    memset(first,-,sizeof(first));
    for (i=;i<=n;i++)
     for (j=;j<=n;j++)
     {
         scanf("%d",&x);
         if (i==) ins(i*n+j,T,x);
         else if (i==n) ins(S,(i-)*n+j,x);
         else ins(i*n+j,(i-)*n+j,x);
     }
    for (i=;i<=n;i++)
     for (j=;j<=n;j++)
     {
         scanf("%d",&x);
         if (j==) ins(S,(i-)*n+,x);
         else if (j==n) ins(i*n,T,x);
         else ins((i-)*n+j,(i-)*n+j+,x);
     }
    for (i=;i<=n;i++)
     for (j=;j<=n;j++)
     {
         scanf("%d",&x);
         if (i==) ins(T,i*n+j,x);
         else if (i==n) ins((i-)*n+j,S,x);
         else ins((i-)*n+j,i*n+j,x);
     }
    for (i=;i<=n;i++)
     for (j=;j<=n;j++)
     {
         scanf("%d",&x);
         if (j==) ins((i-)*n+,S,x);
         else if (j==n) ins(T,i*n,x);
         else ins((i-)*n+j+,(i-)*n+j,x);
     }
    printf("%d\n",dijkstra());
    return ;
}