POJ-3155 : Hard Life
問題概要
無向グラフが与えられる。辺数/頂点数が最大となる部分グラフを求める問題。
解法
fura君に教えてもらった。各辺、頂点に対応する頂点を持つグラフを構成する。このとき、ある辺をとると対応する頂点を必ず選ぶ必要があり、すなわちmaximum closure problemになる。最大化するのはsum{e} / sum{v}なので=gと置いて式変形するとsum{e} - sum{v}*g > 0とできるかどうか調べれば良い。このgは二分探索でできる(平均最大化と同じ)。
acceptされたコード
const int MAX_N = 100; const int MAX_M = 1000; int N, M; int es[MAX_M][2]; bool visited[MAX_N + MAX_M + 2]; double weights[MAX_N + MAX_M + 2]; Graph G; void init() { scanf("%d%d", &N, &M); for (int i = 0; i < M; ++i) { scanf("%d%d", es[i]+0, es[i]+1); --es[i][0]; --es[i][1]; } } double dfs(const int v) { double ans = weights[v]; visited[v] = true; for (int i = 0; i < int(G[v].size()); ++i) { const Edge &e = G[v][i]; const int u = e.to; if (!visited[u] && e.capacity > FLOW_EPS) { ans += dfs(u); } } return ans; } bool check(double test) { G.init(N+M+2); const int source = N + M, sink = source + 1; for (int i = 0; i < N; ++i) { G.addDirectedEdge(i, sink, test); } for (int i = 0; i < M; ++i) { G.addDirectedEdge(source, i+N, 1.0); } for (int i = 0; i < M; ++i) { for (int k = 0; k < 2; ++k) { G.addDirectedEdge(i+N, es[i][k], FLOW_INF); } } memset(visited, false, sizeof(visited)); for (int i = 0; i < N + M + 2; ++i) { if (i < N) { weights[i] = -test; } else if (i < N + M) { weights[i] = 1.0; } else { weights[i] = 0.0; } } calcMaxFlow(G, source, sink); return dfs(source) > FLOW_EPS; } void solve() { if (M == 0) { puts("1\n1"); return ; } double low = 0.0, high = 10000; for (int _ = 0; _ < 50; ++_) { double mid = (high + low) * 0.5; (check(mid) ? low : high) = mid; } check(low); vector<int> ans; for (int i = 0; i < N; ++i) { if (visited[i]) { ans.push_back(i); } } printf("%d\n", int(ans.size())); for (int i = 0; i < int(ans.size()); ++i) { printf("%d\n", ans[i] + 1); } } int main() { init(); solve(); return 0; }