NEERC 2006 Problem H. Hard Life - ヘクトのメモ

この記事はCompetitive Programming (2) Advent Calendar 18日目の記事です.

あまり紹介されていない高度典型問題の解説を書きます.*1

問題文

(追記: 12/18) https://codeforces.com/gym/100287/attachments/download/2012/20062007-acmicpc-northeastern-european-regional-contest-neerc-06-en.pdf
$N$ 頂点， $M$ 辺のグラフが与えられる.
ここで，誘導部分グラフの頂点集合と辺集合をそれぞれ $V，E$ とする.
与えられたグラフの全ての誘導部分グラフのうち， $\frac{|E|}{|V|}$ が最大となる頂点集合 $V$ を1つ求めよ.

ひとこと解法

二分探索 + フロー!

解法

有理数を最大化する問題なので二分探索で答えを探そうと考えます.
ここで基準を $\frac{a}{b}$ とすると，二分探索の判定式は $\frac{|E|}{|V|} > \frac{a}{b}$ となります.
式変形をすると， $b|E| - a|V| > 0$ となります.
この判定式を満たすようなグラフの選び方を求めるために，project selection problem を考えます.
与えられた元のグラフから，以下のようにグラフを作成してs-tフローを流します.
各辺 $e$ が頂点 $u, v$ を結んでいるとした時に次のように辺を貼ります.
f:id:osrehun:20191217231147p:plain
そうすると， $b|E| -$ (このグラフのs-t間の最大フロー)が，考えられる誘導部分グラフの $b|E| - a|V|$ の最大値に対応するので判定が可能になります.
ここで $b|E| - a|V| ≧ 0$ としない理由は，空グラフの $b|E| - a|V|$ は $0$ になり常に条件を満たしてしまうからです.
あとは、二分探索の値域をどうするかという問題がありますが，これはファレイ数列を生成すると良いです.*2
答えとなる頂点集合の復元はフローを流した後のグラフで選択された頂点集合に対応します.
最後に元のグラフが空グラフの時には注意する.
最悪時間計算量は $O((|E| +|V|)^3 \log(|E| +|V|) )$ なんですが，Dinic法は早いので実際には92msで通りました.

コード

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;(i)<(n);++(i))
using namespace std;
 
using ll = long long;
const ll inf = 1LL << 20;
using R = long double;
 
int n, m;
int s, t, all;
 
const int limit = 1500;
int ea[limit], eb[limit];
 
using edge = struct {int to, rev; ll cap, flow;};
vector<edge> graph[limit];
 
void add_edge(int from, int to, ll cap) {
	graph[from].push_back({to, int(graph[to].size()), cap, 0LL});
	graph[to].push_back({from, int(graph[from].size() - 1), 0LL, 0LL});
}
 
int level[limit], iter[limit];
 
bool bfs(int s, int t) {
	fill(level, level + all, -1);
	queue<int> q;
	level[s] = 0, q.push(s);
 
	while (!q.empty()) {
		int v = q.front(); q.pop();
		for (auto &e : graph[v]) {
			if (level[e.to] == -1 and e.cap > e.flow) {
				level[e.to] = level[v] + 1;
				q.push(e.to);
			}
		}
	}
 
	return (level[t] != -1);
}
 
ll dfs(int v, int t, ll f) {
	if (v == t) return f;
	for (int &i = iter[v]; i < graph[v].size(); ++i) {
		edge &e = graph[v][i];
		if (e.cap > e.flow and level[v] < level[e.to]) {
			ll d = dfs(e.to, t, min(f, e.cap - e.flow));
			if (d > 0) {
				e.flow += d, graph[e.to][e.rev].flow -= d;
				return d;
			}
		}
	}
	return 0;
}
 
ll max_flow(int s, int t) {
	const ll INF = 1LL << 30;
 
	while (bfs(s, t)) {
		fill(iter, iter + all, 0);
		while (dfs(s, t, inf) != 0);
	}
 
	ll ret = 0LL;
	for (auto &e : graph[s]) ret += e.flow;
	return ret;
}
 
// bE > aV
// bE - aV > 0
 
bool check(ll a, ll b) {
	rep(i, all) graph[i].clear();
 
	rep(i, n) {
		add_edge(s, i, 0LL);
		add_edge(i, t, a);
	}
 
	rep(i, m) {
		add_edge(s, n + i, b);
		add_edge(n + i, t, 0LL);
		add_edge(n + i, ea[i], inf);
		add_edge(n + i, eb[i], inf);
	}
 
	ll res = b * m - max_flow(s, t);
	return (res > 0LL);
}
 
int main(void) {
	freopen("hard.in", "r", stdin);
	freopen("hard.out", "w", stdout);
 
	cin >> n >> m;
	rep(i, m) {
		cin >> ea[i] >> eb[i];
		ea[i]--, eb[i]--;
	}
 
 
	if (m == 0) {
		cout << 1 << endl;
		cout << 1 << endl;
		return 0;
	}
 
	s = n + m, t = s + 1, all = t + 1;
 
	using state = tuple<R, int, int>;
	vector<state> ary;
	ary.push_back(state(0.0, 0, 1));
 
	for (int a = 1; a <= m; ++a) {
		for (int b = 1; b <= n; ++ b) {
			if (__gcd(a, b) != 1) continue;
			ary.push_back(state(1.0 * a / b, a, b));
		}
	}
 
	sort(begin(ary), end(ary));
 
	{
		const int k = ary.size();
		rep(i, k - 1) {
			int sa, sb;
			tie(ignore, sa, sb) = ary[i];
			int ta, tb;
			tie(ignore, ta, tb) = ary[i + 1];
			ary.push_back(state(1.0 * (sa + ta) / (sb + tb), sa + ta, sb + tb));
		}
	}
 
	sort(begin(ary), end(ary));
 
	int low = 0, high = ary.size();
 
	while (high - low > 1) {
		const int mid = (low + high) / 2;
		int a, b;
		tie(ignore, a, b) = ary[mid];
 
		if (check(a, b))
			low = mid;
		else
			high = mid;
	}
 
	{
		int a, b;
		tie(ignore, a, b) = ary[low];
		check(a, b);
	}
 
	vector<int> ans;
 
	rep(v, n) {
		bool used = false;
		if (level[v] != -1) ans.push_back(v + 1);
	}
	
 
	cout << ans.size() << endl;
	for (auto &elem : ans) cout << elem << endl;
 
	return 0;
}

感想

この問題のフレームワークは割と汎用性があると個人的に思います.
問題設定をハイパーグラフにしても問題を解けるし，具体性のあるストーリーを与えてあげると解法が思いつきにくいなぁと.
ICPCの現役時代に解いたので，解説を書きたいなと思いつつ2年も経ってしまったことにビックリしています.
本当にビックリなのは2006年のICPCのコンテストでこのクオリティの問題を出題していることですね...... NEERC恐るべし.
ICPCの現役選手は余力があればアジア以外の海外リージョンも解いてみると楽しいと思います.

*1:hosさんのスライドで初めてこの問題を知りました.http://hos.ac/slides/20150319_flow.pdf

*2:具体的には分母 100 までのファレイ数列を生成すると良い.