http://poj.org/problem?id=2987
はじめてフローでまともな問題解いたかもしれない。
maximum closure problemという有名問題。↓wiki参照。
https://en.wikipedia.org/wiki/Closure_problem
何個使うかも答えなければいけないが、それはmin-cutを得る際の(cap>0)の辺のみを追っていくdfsでできる。
bool used[MAX_N]; void group(int v) { used[v] = true; rep(i, 0, (int)G[v].size()) { int n = G[v][i].to; if(!used[n] && G[v][i].cap > 0) { group(n); } } } int N, M; int main() { scanf("%d%d", &N, &M); int s = 0, t = N + 1; ll sum = 0; rep(i, 0, N) { int a; scanf("%d", &a); if(a > 0) { add_edge(s, i + 1, a); sum += a; } else add_edge(i + 1, t, -a); } rep(i, 0, M) { int a, b; scanf("%d%d", &a, &b); add_edge(a, b, inf); } ll res = sum - max_flow(s, t); group(0); int g = 0; rep(i, 0, N + 2) g += used[i]; if(res < 0) printf("0, 0\n"); else printf("%d %lld\n", g - 1, res); return 0; }
なんかフローって不思議な感じがする…。
この問題も直観的には理解できてない…。