網頁

2014年4月18日 星期五

POJ 2455 Secret Milking Machine

題意:
    有N個點(編號1~N)組成無向圖,總共有P條邊,要找出從編號1走到編號N共T條路徑(也就是有T條從1~N的路徑),使得這T條路徑最長的那條為最小。假設T條中最長的那條路徑長為D,我們要找出D的最小値。
     輸入第一行分別為N P T,接下來有P行,每行u v d表示有一條u到v距離為d的邊,注意u到v可能會有很多條邊,且這T條路徑不能重邊。

想法:
    二分搜尋+最大流,用二分去找D値,每次二分時就重新建一個新的圖,建圖方法為假設dis[u][v]<=D,就把[u][v]容量+1,建完圖後做最大流並確認是否有T條路徑,如果有則D値可以再小,如果沒有則要把D値加大。



沒有留言:

張貼留言