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