PKU3263-Tallest Cow

題目：http://poj.org/problem?id=3263
FJ有N(10000)頭牛一字排開，每頭牛有各自的正整數高度
並且已知最高的l號牛的高度是H
再來給出R條「某u牛能看見某v牛」的關係
代表著
1.h[u]<=h[v]
2.其他介於u...v之間的x都滿足h[x]<h[u]
一定存在滿足所有約束條件的解，問每一頭牛最高可能是多高



程式碼：codepad掛了，待補

【解法一：差分約束系統】
由於題目說了高度都是「正整數」，所以對某個關係"u看見v"可以解讀成：
1.h[u]<=h[v]
2.其他介於u...v之間的x都滿足h[x]<=h[u]-1

一開始把所有最短路徑值設定H，對所有的x建邊(u->x距離-1)、v->u距離0

邊數最多可能接近1+2+3+...+10000=5000萬

這時如果用傳統的BellmanFord O(VE)顯然超時

但是題目保證了沒負環，SPFA能造成很大優化，總時間0.9秒通過





【解法二：被線段覆蓋的次數】

題目保證了沒負環

解答一定存在，所以…

首先我們希望所有牛盡可能高，都設定其高度值為H

那麼每頭牛到底確切要多高呢？

答案就是根據它到底「小於別人幾次」，從H裡扣掉

問題變成了，每個點到底被區間(u,v)蓋到了幾次？

想像它們按照開始時間u排序
每次u進來「目前高度」-1、每次u結束「目前高度」+1
最後得到網路上廣為流傳的線性作法

整支程式非常精巧：
1.確定(u,v)有u<v否則互換
2.過濾掉重複的(u,v)
3.令一個陣列a[]，每條(u,v)都操作a[u+1]-- , a[v]++
4.各牛高度值的答案就是a[1]+a[2]+...+a[x]+H