POJ 3155: Hard Life

http://poj.org/problem?id=3155

良問だと思う。

hardness factorがkの時実現可能か考える。
辺と点を対応させた二部グラフを作る。
辺からそれが含む点に対して辺をはる。
そして辺にコスト1,点にコスト-kをつけると、Maximum Closure Problemに帰着できるので、
あとはPOJ 2987と同じようにグラフを構成し、「得られた値が0より大きい<=>kの時実現可能」となるから
kをにぶたんで求めることが出来る。

あとはcap>0が成立する辺のみでdfsすることで求めるべき点の集合を得られる。

フローのcapの型をdoubleにし忘れないように。

namespace MF { //init before you use it. when you use double, be careful
	struct edge { int to; double cap; int rev; };

	vector<edge> G[MAX_N];
	int level[MAX_N];
	int iter[MAX_N];

	void init(int n) {
		rep(i, 0, n) G[i].clear();
		memset(level, 0, sizeof(level));
		memset(iter, 0, sizeof(iter));
	}

	void add_edge(int from, int to, double cap) {
		G[from].push_back((edge){to, cap, (int)G[to].size()});
		G[to].push_back((edge){from, 0, (int)G[from].size() - 1});
	}

	void bfs(int s) {
		memset(level, -1, sizeof(level));
		queue<int> que;
		level[s] = 0;
		que.push(s);
		while(!que.empty()) {
			int v = que.front(); que.pop();
			for(int i = 0; i < (int)G[v].size(); i++) {
				edge &e = G[v][i];
				if(e.cap > 0 && level[e.to] == -1) {
					level[e.to] = level[v] + 1;
					que.push(e.to);
				}
			}
		}
	}

	double dfs(int v, int t, double f) {
		if(v == t) return f;
		for(int &i = iter[v]; i < (int)G[v].size(); i++) {
			edge &e = G[v][i];
			if(e.cap > 0 && level[v] < level[e.to]) {
				double d = dfs(e.to, t, min(f, e.cap));
				if(d > 0) {
					e.cap -= d;
					G[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}

	double get(int s, int t) {
		double flow = 0;
		while(true) {
			bfs(s);
			if(level[t] == -1) return flow;
			memset(iter, 0, sizeof(iter));
			double f;
			while((f = dfs(s, t, inf)) > 0) {
				flow += f;
			}
		}
	}
}

int N, M;

int A[1010], B[1010];
bool used[1110];

void dfs(int v) {
	used[v] = true;
	rep(i, 0, (int)MF::G[v].size()) {
		MF::edge& e = MF::G[v][i];
		if(e.cap >= eps && !used[e.to]) {
			dfs(e.to);
		}
	}
}

bool ok(double m) {
	MF::init(N + M + 2);
	int s = N + M, t = N + M + 1;
	rep(i, 0, M) {
		MF::add_edge(i + N, A[i], inf);
		MF::add_edge(i + N, B[i], inf);
	}
	rep(i, 0, N) MF::add_edge(i, t, m);
	rep(i, 0, M) MF::add_edge(s, i + N, 1);
	double ans = MF::get(s, t);
	double res = (double)M - ans;
	return res >= eps;
}

int main() {
	scanf("%d%d", &N, &M);
	rep(i, 0, M) {
		scanf("%d%d", &A[i], &B[i]);
		A[i]--;
		B[i]--;
	}

	double lv = 0, rv = M;
	while(rv - lv > eps) {
		double m = (lv + rv) / 2;
		if(ok(m)) lv = m;
		else rv = m;
	}
	ok(lv);
	dfs(N + M);
	if(M != 0) {
		int res = 0;
		rep(i, 0, N) res += used[i];
		printf("%d\n", res);
		rep(i, 0, N) {
			if(used[i]) printf("%d\n", i + 1);
		}
	}
	else {
		printf("1\n1\n");
	}


	return 0;
}

最小費用流にやっと入れる…。