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的
No comments:
Post a Comment