ACMLib

Hard Life

June 10, 2017

Дисклеймер

Статья содержит решение задачи H. Hard Life с NEERC-2006. Если вы планируете в будущем играть этот контест и не хотите портить себе удовольствие, то читать статью не рекомендуется.

Пререквизиты

• Задача о максимальном потоке
• Теорема Форда-Фалкерсона

Условие задачи

Плотностью неориентированного графа назовём отношение количества рёбер к количеству вершин.

Дан неориентированный граф без петель и кратных рёбер. Найти в нём индуцированный подграф максимальной плотности. Другими словами, нужно найти множество вершин $V$ такое, что $\frac{| E(V) |}{ | V | }$ максимально, где $E(V)$ — множество рёбер графа, у которых оба конца лежат в $V$.

Ограничения

$1 \le n \le 100$, $0 \le m \le 1000$, где $n$ — количество вершин графа, $m$ — количество рёбер графа.

Решение

Сделаем двоичный поиск по ответу.

Теперь при фиксированном $\sigma$ мы хотим проверить, что существует подграф с плотностью строго больше $\sigma$, то есть $| E(V) | - \sigma | V | > 0$. Это неравенство эквивалентно неравенству $2 \sigma | V | + 2 \left( m - | E(V) | \right) < 2m$.

Сейчас мы построим $V$ так, чтобы минимизировать $2 \sigma | V | + 2 \left( m - | E(V) | \right)$. Потом этот минимум нужно будет просто сравнить с $2m$.

Построим сеть, в которой будут фиктивные исток и сток S и T, а также все вершины исходного графа. Цель — получить такую сеть, что если мы возьмём разрез между S и T такой, что к T мы отнесём множество $V$ вершин исходного графа, то стоимость этого разреза будет как раз $2 \sigma | V | + 2 \left( m - | E(V) | \right)$. Тогда задача сведётся к поиску минимального разреза в этой сети, а значит и к поиску максимального потока из S в T (по теореме Форда-Фалкерсона).

Мы хотим платить

1. $2 \sigma$ за каждую вершину, которую мы отнесли в $V$;
2. $2$ за каждое ребро, которое имеет хотя бы один из концов вне $V$.

С первым пунктом справиться легко: мы должны из $S$ провести ребро с пропускной способностью $2 \sigma$ в $v$.

Со вторым пунктом поступим хитрее. Будем платить $deg(v)$ за каждую вершину $v$, которую мы не отнесли в $V$. Тогда за все рёбра, у которых оба конца лежат вне $V$, мы заплатим дважды по $1$ (что мы и хотели), а за рёбра, у которых только один конец лежит в $V$, мы заплатим $1$ только единожды. Но такие по таким рёбрам как раз проходит разрез, что позволяет нам получить такую сеть:

1. Из $S$ в $v$ ребро пропускной способности $2 \sigma$;
2. Из $v$ в $T$ ребро пропускной способности $deg(v)$;
3. Для каждого ребра $(uv)$ исходного графа рёбра пропускной способности $1$ из $u$ в $v$ и из $v$ в $u$.

Восстановление ответа

Понятно, что нужно просто найти в явном виде разрез для критического значения $\sigma$ и вывести соответствующее множество $V$. Но стоить быть аккуратным, ведь всегда можно взять $V$ пустым, стоимость соответствующего разреза будет ровно $2m$. Поэтому нужно немного уменьшить $\sigma$, чтобы существовал нетривиальный ответ, для которого стоимость разреза будет строго меньше.

Также нужно не забыть про случай $m=0$, когда хороших вариантов вообще не существует, и прописать его руками.

Сложность

Разность между двумя разными рациональными числами со знаменателем не больше $n$ не может быть меньше, чем $n^{-2}$, следовательно, такая же нам нужна точность (в бинарном поиске). Тогда количество итераций будет $O \left( \log n \right)$. Итоговая сложность — $ O \left( T(n + 2, 2m + 2n) \log n \right) $, где $T(n, m)$ — сложность используемого алгоритма поиска максимального потока. Если для поиска максимального потока использовать алгоритм Диница, то итоговая сложность будет $ O \left( n^{2} (n+m) \log n \right) $.

Код

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
const int N = 104;
const int M = 1010;
const int IT = 40;

struct Flow
{
	Flow(int n); //initialize with empty network on n vertices
	void addEdge(int v, int to, double cap); //adds edge v->to with capacity cap
	double getFlow(); //returns maximum flow
};

int n, m;
int edges[M][2];
int deg[N];

Flow buildFlow(double sigma)
{
	Flow flow = Flow(n + 2);
	int S = n, T = n + 1;
	for (int v = 0; v < n; v++) {
		flow.addEdge(S, v, 2 * sigma);
		flow.addEdge(v, T, deg[v]);
	}
	for (int i = 0; i < m; i++) {
		flow.addEdge(edges[i][0], edges[i][1], 1);
		flow.addEdge(edges[i][1], edges[i][0], 1);
	}
	return flow;
}

void restoreAns(double sigma); //print answer

void read()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
		for (int j = 0; j < 2; j++) {
			scanf("%d", &edges[i][j]);
			edges[i][j]--;
			deg[edges[i][j]]++;
		}
}

int main()
{
	read();

	if (m == 0) {
		printf("1\n1\n");
		return 0;
	}

	double l = 0, r = m;
	for (int it = 0; it < IT; it++) {
		double sigma = (l + r) / 2;
		if (buildFlow(sigma).getFlow < 2 * m - eps)
			l = sigma;
		else
			r = sigma;
	}

	restoreAns(r - 1. / (2 * n * n));

	return 0;
}

Использование при решении других задач

Определим плостность массива длины $n$ как количество инверсий (пар $1 \le i < j \le n$ таких, что $a_{i} > a_{j}$), делённое на $n$. Дан массив длины $m \le 60$, найти в нём подпоследовательность максимальной плотности.

Можно построить граф, соединив ребром элементы, которые образуют инверсию. Тогда в задаче требуют найти подграф максимальной плотности.

Забавный факт: эта задача называлась This Problem Needs 3D Arrays, хотя авторское решение использовало сведение к Hard Life.