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; }
最小費用流にやっと入れる…。