POJ 2987: Firing

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;
}

なんかフローって不思議な感じがする…。
この問題も直観的には理解できてない…。