ProjectSelection

keyword:

カートに追加

overview

project p_1..p_n があり,それぞれのprojectは状態Bである. 今,いくつかのpeojectを状態Aに移すことができる. - (i, r) p_iが状態Aの時,利益(損失)rを得る. - (i, j, q)p_iが状態Aでp_jが状態Bの時,qの損失が発生する. 利益を最大化する. 燃やす埋めるフローの考察の補助に使うことができる..

usage

void push_revenue(int i, DGraphF::cap_t r)
;p_iが状態Aの時,利益(損失)rを得る.
void push_purchase(int i, int j, DGraphF::cap_t q)
;p_iが状態Aでp_jが状態Bの時,qの損失が発生する.
DGraphF::cap_t solve()
解く.

verified

verified(ARC)

references

https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem#Project_selection_problem
http://tokoharuland.hateblo.jp/entry/2017/11/12/234636

require

code