?
分析：非常非常好的一道題！
首先需要對問題進行轉化：
- 行列無關，對于行單獨處理，對于列單獨處理
- 必然存在一個最優方案使得每一個新站與舊站重合.
轉化1很顯然，對于轉化2，是一類非常經典的“中位數問題”,即在一條線段上，有若干個特殊點，要選擇一個點的位置，使得它到這些點距離*對應權值的和最小. 結論就是這個點一定在給定的這些點的位置上.
那么問題可以變成，m個位置，每個有n種選擇，代價即為其與舊站的傳輸代價和。不同位置間的選擇也會帶來代價.
首先假設我們不知道這道題要用網絡流來做. dp? Emm,這怎么設計狀態啊，要狀壓嗎？ 明顯壓不下. 貪心，肯定不行. 這道題涉及到“匹配”，自然就是網絡流咯.
費用流可以嗎？顯然是不行的，舊站與新站之間的費用很好處理，但是新站與新站之間的費用不好處理.
那就只有是最大流咯. 用流量表示費用？這怎么表示啊......
那么鎖定方法--最小割！
每個位置有多種選擇,注意到這句話，可以往兩個方面去想：
- 把選擇看作點.
- 將每個位置拆成選擇個數個點.
本題如果要用最小割顯然不能用第一種方法.因為選擇與選擇之間不好處理，那么就用第二種方法.
上面所畫的就是建圖方式.具體說來，就是S連向每個點拆出來的第一個點，容量為inf,每個點拆出來的最后一個點連向T，容量為inf.
對于第i個點拆出的第k個點連向第i個點拆出的第k+1個點，容量為第i個新站建在第k個舊站的代價.
對于第i個點拆出的第k個點連向第j個點拆出的第k個點，容量為b_ij.
下面來分析一下建圖：
割掉第i個點拆出來的點實際上就是確定了第i個新站的位置. 如上圖所示，如果同時割掉兩條紅色的邊，為了使得S,T不連通，必然會割掉兩條綠色的邊. 如果i的選擇是pi,j的選擇是pj,一共會割掉 |pi - pj|條綠邊，正好就是新站i,j之間的代價.
至此這道題就做完了.
一點感想：最小割為了使得ST不連通，一次能夠割掉很多條邊.如果網絡流的題要求很多的貢獻（兩兩之間的）.嘗試用最小割？
)
)
