POJ-2987 : Firing

問題概要

maximum closure problemの最適解と、それを達成するために必要な最小頂点数を求める問題。

解法

よく知られているように、最小カットでsource側に分離される頂点が答。最小性の証明についてはよく理解できていない。

acceptされたコード

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

typedef long long int64;
const int64 INF = int64(1.05e18); 

typedef int64 flow_t;

const int MAX_N = 5000;

int N, M;
Graph G;
int weights[MAX_N];
bool visited[MAX_N + 2];

void init() {
	scanf("%d%d", &N, &M);
	G.init(N + 2);
	for (int i = 0; i < N; ++i) {
		scanf("%d", weights + i);
	}
	for (int _ = 0; _ < M; ++_) {
		int from, to;
		scanf("%d%d", &from, &to);
		--from; --to;
		G.addDirectedEdge(from, to, INF);
	}
}

void dfs(int v) {
	visited[v] = true;
	for (int i = 0; i < int(G[v].size()); ++i) {
		const Edge &e = G[v][i];
		if (e.capacity > 0 && !visited[e.to]) {
			dfs(e.to);
		}
	}
}

void solve() {
	const int source = N, sink = source + 1;
	for (int i = 0; i < N; ++i) {
		if (weights[i] > 0) {
			G.addDirectedEdge(source, i, weights[i]);
		}
		else if (weights[i] < 0) {
			G.addDirectedEdge(i, sink, -weights[i]);
		}
	}
	calcMaxFlow(G, source, sink);
	dfs(source);
	int64 ans = 0;
	int cnt = 0;
	for (int i = 0; i < N; ++i) {
		if (visited[i]) {
			++cnt;
			ans += weights[i];
		}
	}
	printf("%d %lld\n", cnt, ans);
}

int main() {
	init();
	solve();
	return 0;
}