ZOJ 2676 Network Wars

Problem statement: Given a undirected graph, each edge has a cost c, select k edges to disconnect vertex 1 and N, the goal is to minimize c/k

直覺是 binary search 答案
對每條edge, 如果 cost[x][y] < mid, 則直接選取
對餘下的 edge 做 flow 搵 min cut

算法不難想到, 比較挑戰的是 handle precision
發現有些位寫

R < 1e-8 WA
R <= 0 AC

後來想到可能是因為做 flow 的部份和用 dfs 搵 cut set 的 handle 方法要一致

係段 code 既邊個位用 epsilon 也要小心處理