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 也要小心處理

Team Training 13/10/2010 - Phuket 2009

Training 時做不到 K, 在 Joe 的指點下現在做到了
是帶cost的lower bound flow

Problem statement:
Given a directed graph, each edge has 2 cost: Patrol cost and Video cost. Each edge must be either patrol or video, the in-degree of patrol road must equals the out-degree of patrol road on each node. Some edges are pre-assigned to be patrol road. At least one road must be patrolled.

看下去很多條件..
入度和出度其實implies patrol edge是一個個的cycle
所以題目其實是要找一些patrol cycle 去 minimize total cost

先假設所有edge都是video, 每條edge的cost便是轉為patrol的費用

第一步是滿足有些edge必定是patrol的條件
用lower bound做circulation
先不用理cost, 找一個任意的feasible flow

第二步處理cost
其實就是不斷在residual network找negative cycle
用bellman-ford做時, 要注意即使第V個iteration update了node x 並不implies node x 是在 negative cycle 中

最後處理at least one edge must be patrolled
即係搵minimum cycle
由於沒有限定cycle length一定要>2, 可以直接用floyd-warshall做


做完這題終於搞清了lower bound flow的一些概念
有Source和Sink的graph如果有cycle做lower bound flow是NP的

Team Training 11/10/2010 - SWERC 2006

Team Training 7/10/2010 - NWERC 2004

Team Training 5/10/2010 - Danang 2007