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