題目大意：有一條東西向流淌的河，寬為W，河中有N塊石頭，每塊石頭的坐標(Xi, Yi)和最大承受人數Ci已知。現在有M個游客在河的南岸，他們想穿越這條河流，但是每個人每次最遠只能跳D米，每跳一次耗時1秒。問他們能否全部穿越這條河流，如果能，最少需要多長時間。（0 <= N <= 50, 0 < M <= 50, 0 <= D <= 1000, 0 < W <= 1000, 0 < Xi < 1000, 0 < Yi < W, 0 <= Ci <= 1000）

?

題解：動態流的基礎題了吧。首先想到MCMF，發現wa了。。。然后想了一會發現是因為每個人是可以不跳的，所以就只能很悲哀的對時間拆點上動態流了。

接下來的敘述忽略石頭的拆點Ci，連接邊全都不大于D這兩條限制條件。

對于t時刻，我們先連接超級源點到t時刻的石頭（代表了蹲了t-1個時候的現在爆發的人。。。），然后連接t-1時刻石頭到超級匯點（代表可以沖過終點線的人，注意不是t時刻是因為那些人還需要用這一秒鐘來沖到對岸呢），然后連接t-1時刻的石頭到t時刻的石頭（代表往前走了一步的）。然后對于每一個時刻跑最大流，如果等于人數了就行了。

那么時間的上限呢？不難想到是n+m的：每個人都走一遍所有的石頭，一個人接在一個人的后面，就n+m了，不可能比這個時間還多。

然后注意一下這道題的很多細節：我們要處理出所有兩點間距離，同時由于河岸是一條直線要特別計算。。。同時還要對石頭拆點，精細計算每一個石頭的點編號別沖突了，，，稍稍不注意就會寫錯。。。

總而言之呢，這道題還是極好的。

轉載于:https://www.cnblogs.com/chxer/p/4573127.html

總結

以上是生活随笔為你收集整理的SGU 0438 The Glorious Karlutka River =) 动态流的全部內容，希望文章能夠幫你解決所遇到的問題。

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