2007: [Noi2010]海拔
Time Limit: 20 Sec Memory Limit: 552 MB
Submit: 2504 Solved: 1195
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
2
3
4
5
6
7
8
Sample Output
【樣例說明】
樣例資料見下圖。
最理想情況下所有點的海拔如上圖所示。
對于100%的資料：1 ≤ n ≤ 500，0 ≤ 流量 ≤ 1,000,000且所有流量均為整數。
HINT
Source
【分析】
跟狼抓兔子差不多？
首先，大膽地考慮一下隻有1和0？【如果不是，你可以假設一下隻有一個點不是，周圍都是，然後往好的地方修改，至少不會變差的】
當然你也不會無聊到1，0，1，0，交替。。不然累死人【其實最好就是都是平的，但是規定了兩個角是有高度差的】
是以隻要找到0，1分界線，就變成了最小割了。
但這種圖嘛，可以轉化成成對偶圖，跑最短路就好了【别人說卡spfa？但是我過了】
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 #include<algorithm>
6 #include<queue>
7 using namespace std;
8 #define Maxn 510
9
10 int num[Maxn][Maxn],cnt;
11
12 struct node
13 {
14 int x,y,c,next;
15 }t[Maxn*Maxn*20];
16 int first[Maxn*Maxn*2],len;
17 void ins(int x,int y,int c)
18 {
19 // printf("%d -> %d %d\n",x,y,c);
20 t[++len].x=x;t[len].y=y;t[len].c=c;
21 t[len].next=first[x];first[x]=len;
22 }
23
24 queue<int > q;
25 bool inq[Maxn*Maxn*4];
26 int dis[Maxn*Maxn*4],st,ed;
27 bool spfa()
28 {
29 while(!q.empty()) q.pop();
30 memset(inq,0,sizeof(inq));
31 for(int i=1;i<=ed;i++) dis[i]=-1;
32 inq[st]=1;dis[st]=0;
33 q.push(st);
34 while(!q.empty())
35 {
36 int x=q.front();
37 for(int i=first[x];i;i=t[i].next)
38 {
39 int y=t[i].y;
40 if(dis[y]==-1||dis[y]>dis[x]+t[i].c)
41 {
42 dis[y]=dis[x]+t[i].c;
43 if(!inq[y])
44 {
45 q.push(y);
46 inq[y]=1;
47 }
48 }
49 }q.pop();inq[x]=0;
50 }
51 if(dis[ed]==-1) return 0;
52 return 1;
53 }
54
55 int main()
56 {
57 int n;
58 scanf("%d",&n);
59 for(int i=1;i<=n;i++)
60 for(int j=1;j<=n;j++) num[i][j]=++cnt;
61 for(int i=1;i<=n;i++) num[i][0]=cnt+1;
62 for(int i=1;i<=n;i++) num[n+1][i]=cnt+1;
63 len=0;
64 memset(first,0,sizeof(first));
65 for(int i=1;i<=n+1;i++)
66 for(int j=1;j<=n;j++)
67 {
68 int x;scanf("%d",&x);
69 ins(num[i-1][j],num[i][j],x);
70 }
71 for(int i=1;i<=n;i++)
72 for(int j=1;j<=n+1;j++)
73 {
74 int x;scanf("%d",&x);
75 ins(num[i][j],num[i][j-1],x);
76 }
77 for(int i=1;i<=n+1;i++)
78 for(int j=1;j<=n;j++)
79 {
80 int x;scanf("%d",&x);
81 ins(num[i][j],num[i-1][j],x);
82 }
83 for(int i=1;i<=n;i++)
84 for(int j=1;j<=n+1;j++)
85 {
86 int x;scanf("%d",&x);
87 ins(num[i][j-1],num[i][j],x);
88 }
89 st=0;ed=cnt+1;
90 // st=cnt+1;ed=0;
91 spfa();
92 printf("%d\n",dis[ed]);
93 return 0;
94 } View Code
2017-03-29 08:11:42
平面圖轉對偶圖總結：
轉自:http://blog.sina.com.cn/s/blog_60707c0f01011fnn.html
一個圖G=(V,E)，若能将其畫在平面上，且任意兩條邊的交點隻能是G的頂點，則稱G可嵌入平面，或稱G是可平面的。可平面圖在平面上的一個嵌入稱為一個平面圖。如下圖左邊黑色的圖為平面圖，右邊紅色的圖不屬于平面圖：
由平面圖的邊包圍而成，其中不含圖的頂點。也稱為面。包圍面R的所有邊組成的回路稱為該面的邊界，回路長度稱為該面的度，記為deg(R)。具有相同邊界的面稱為相鄰面。由平面圖的邊包圍且無窮大的面稱為外部面。一個平面圖有且隻有一個外部面。如下面的平面圖中，R0是外部面R0與R1, R2, R3均相鄰。deg(R0)=8, deg(R1)=4, deg(R2)=5（R2經過的頂點序列為v7-v4-v6-v4-v5-v7）, deg(R3)=1：
利用歐拉公式和數學歸納法可以證明平面圖G的所有面的度之和等于其邊數|E|的2倍，即：
下面我們引入對偶圖，設有平面圖G=(V,E)，滿足下列條件的圖G'= (V',E') 稱為圖G的對偶圖：G的任一面Ri内有且僅有一點Vi'；對G的域Ri和Rj的共同邊界Ek，畫一條邊Ek'=(Vi',Vj')且隻與Ek交于一點；若Ek完全處于Ri中，則Vi'有一自環Ek'，如下圖G'是G的對偶圖：
1 最大流的應用
如果網絡流中的圖G可以轉化為一個平面圖，那麼其對偶圖G'中的環對應G中的割，利用最大流最小割定理轉化模型，根據平面圖G'與其對偶圖的關系，先求出最小割。首先連接配接s和t，如下圖藍色虛線，得到一個附加面，我們設附加面對應的點為s'，無界面對應的點為t'，求該圖的紅色的對偶圖G'，最後删去s'和t'之間的邊：
一條從s'到t'的路徑，就對應了一個s-t割，更進一步，如果我們令每條邊的長度等于它的容量，那麼最小割的容量就等于最短路的長度。這樣時間複雜度大大降低了。
注意 如果是有向邊，那麼就統一順時針旋轉90度