MAXimal

���������: 13 Aug 2010 19:48
�������������: 14 Jun 2012 5:01

���������� [������]

�������� ������

���������� ������

����� ���� ����, �.�. ��������������� ���� G, � ������� ������� ����� (u,v) ��������� ���������� ����������� c_{uv}, � ����� �������� ��� ������� — ����� s � ���� t.

��������� ����� � ���� ���� ����� f_{uv} �� ������ s � ���� t ������������ ��������.

������� �������

���� �������� ��� ����������� ��������� (�����������) ������ ������ ������� (Yefim Dinic, ������ ������� ��� "Dinitz") � 1970 �., �.�. ���� �� ��� ���� ������ ������������� ��������� ��������-����� (�������, ��� ��������� ���� ���������� ������� � 1968 �.).

����� ����, ������� ��������, ��� ��������� ��������� ��������� ���� ����������� ������� ������ (Shimon Even) � ��� �������� ������ ���� (Alon Itai) � 1979 �. ������ ��������� �� �������� ������� ���� ����������� �����: ��� ��������� � ���� ������ ��������� ����������� ������� ���������� ��������� (Alexander Karzanov, 1974 �.), � ����� ����������������� �������� � ��� ���������� ������ � ������ � � �������, � ������� ������ ���� �������� � ���������� �����.

�������� ���� �� ��������� � ��������� ���������� ������ ��������� �������������, �������� "�������� �������" ��� ���, ����������� ���� � �����. �����, ��� ������ ������� ���� ���������� ����� ������������ (��� � ������ ��������� ������ � ��������� ��������-�����), ������, ���� ��� ���� ������ ������������� (�������� ������ �� ���� ������� �������); ������ ��, ��������, ��������� ���� �� ���� ������� "��������" ��������� ����������� ��� �� ������ ������� ����� ��� �� ����������� (��� �������� ��������� ������������� � 1974 �. � �������� ���������� (Goldberg) ������������� � 1985 �.).

����������� �����������

����� ��� ����������� ����������� (������ �� ��� �������� ����������� �� ���������), ������� ����� ����� �������������� � ��������� ������.

���������� ����� G^R �� ��������� � ���� G � ���������� ������ f � ��� ���������� ����, � ������� ������� ����� (u,v) \in G � ���������� ������������ c_{uv} � ������� f_{uv} ������������� ��� �����:

  • (u,v) � ���������� ������������ c_{uv}^R = c_{uv} - f_{uv}

  • (v,u) � ���������� ������������ c_{vu}^R = f_{uv}

����� ��������, ��� ��� ����� ����������� � ���������� ���� ����� ���������� ������� ����: ���� � �������� ���� ���� ��� ����� (u,v), ��� � (v,u).

���������� ����� ����� ���������� �������� ��� ���� ����, ��������� ��� ����� ��������� ����� ����� ������-�� �����. � ����� ����, ���� �� ����� (u,v) � ���������� ������������ c_{uv} ��������� ����� f_{uv}, �� ������������ �� ���� ����� ���������� ��� c_{uv}-f_{uv} ������ ������, � � �������� ������� ����� ���������� �� f_{uv} ������ ������, ��� ����� �������� ������ ������ � �������������� �����������.

����������� ������� � ������ ���� ���������� ����� �����, ��� ����� ���� �� ������ s � ���� t �������� ���������� ���� ������� �����. ����� �������, � ������ ���� �� ������� ������ ���� �� ������ � ����, ����� �������� ����� ���������������� ��������� �����.

����������� ����� �� ����������� ����������. ������� �����-���������� ������� � ���, ��� ����� ����� ������������ ����� � ������ �����, ����� � ���������� ���� �� ������� s-t ����; � ����������� �� ������ ������ �� ������������ � ������������� ���� �� �����, ������������ � ���������� ����.

�������� ���� ��� ������ ���� �������� ��������� �������. ������� ������������ ����� ���������� ����� �� ������ s �� ���� ��������� ������; ������ ������� {\rm level}[v] ������� � ���������� �� ������. ����� � �������� ���� �������� ��� �� ���� (u,v) �������� ����, ������� ����� � ������ ������ �� �����-���� ������, ����� �������, �������, �.�. {\rm level}[u] + 1 = {\rm level}[v] (������ � ���� ������ ������� ���������� �� ����� ������������ �������, ������� �� �������� ���������� ����������). ����� �������, ��������� ��� ����, ������������� ������� ������ �������, � ����� ����, ������� �����, � ���������� �������.

��������, �������� ���� ���������. ����� ����, ����� s-t ���� � �������� ���� �������� ���������� ���� � �������� ����.

��������� �������� ���� �� ������ ���� ����� �����: ��� ����� ���� ��������� ����� � ������ �� ����� ���� ����, �������� ��� ����� ��� ������ ������� �������� {\rm level}[], � ����� ������ � �������� ���� ��� ���������� ����.

����������. ������ "�������� ����" � ������������� ���������� �� �������������; ������ ��� ����������� ���������� ������ "��������������� ������". �������, �� ���������� ����� ������ ������������ ������ "layered network".

��������

����� ���������

�������� ������������ ����� ��������� ���. �� ������ ���� ������� �������� ���������� ����, ����� �� ��������� � ��� �������� �������� ���� (������� � ������), � � ��� ������ ������������ ����������� �����. ��������� ����������� ����� ������������ � �������� ������, � �� ���� ��������� �������� �������������.

���� �������� ���� � ���������� ��������-�����, �� �������� ������� ����� �������� ���: �� ������ �������� ����� ������������� �� ����� ������ ����������� s-t ����, � ����� ������ ������ ����� ����� (���� ������ ������ ������ � �������� ���� � ����������� ������ �������� ����).

������������ ���������

�������, ��� ���� �������� �����������, �� �� ������ � ���� ���������� ����� ������ ������������ ��������.

� ����� ����, �����������, ��� � �����-�� ������ � �������� ����, ����������� ��� ���������� ����, �� ������� ����� ����������� �����. ��� ��������, ��� ���� t ������ �� �������� � �������� ���� �� ������ s. �� ��������� �������� ���� �������� � ���� ��� ���������� ���� �� ������ � ���������� ����, ��� � ���� ������� ��������, ��� � ���������� ���� ��� ���� �� ������ � ����. �������������, �������� ������� �����-����������, ��������, ��� ������� ����� � ����� ���� ����������.

������ ����� ���

�������, ��� �������� ������ ������ ��������� ����� n ���. ��� ����� ������� ��� �����:

����� 1. ���������� ���������� �� ������ �� ������ ������� �� ����������� � ����������� ������ ��������, �.�.

 {\rm level}_{i+1}[v] \ge {\rm level}_i[v]

��� ������ ������ ���������� ����� ����, ����� ������� ����� �������� ���� ����������.

��������������. ����������� ������������ ���� i � ������������ ������� v � ���������� ����� ���������� s-v ���� P � ���� G^R_{i+1} (��������, ��� �� ���������� ���������� ����, ������ ����� ����������� i+1-�� ����). ��������, ����� ���� P ����� {\rm level}_{i+1}[v].

�������, ��� � ���������� ���� G^R_{i+1} ����� ������� ������ ���� �� G^R, � ����� ����, �������� ����� �� G^R (��� ������� �� ����������� ���������� ����). ���������� ��� ������:

  • ���� P �������� ������ ���� �� G^R. �����, �������, ����� ���� P ������ ���� ����� {\rm level}_i[v] (������ ��� {\rm level}_i[v] �� ����������� — ����� ����������� ����), ��� � �������� ���������� �����������.
  • ���� P �������� ��� ������� ���� �����, �� ������������ � G^R (�� �������� ������-�� ����� �� G^R). ���������� ������ ����� �����; ����� ��� ����� ����� (u,w).

     s \Longrightarrow u \rightarrow w \Longrightarrow[...]

    �� ����� ��������� ���� ����� � ������� u, ������ ��� ��� ��������� ��� ������ ������; ����, �� �������� ����������� {\rm level}_{i+1}[u] \ge {\rm level}_i[u].

    ������ �������, ��� ��������� ����� (u,w) ��������� � ���������� ���� ������ ����� ���������� i-�� ����, �� ������ �������, ��� ����� ����� (w,u) ��� ������������� �������� �����-�� �����; �������������, ����� (w,u) ������������ �������� ���� ����� i-�� �����, � ������ {\rm level}_i[u] = {\rm level}_i[w] + 1. ����, ��� �� �������� ���������� ����� {\rm level}_{i+1}[w] = {\rm level}_{i+1}[u] + 1, � ��������� ��� ��������� � ����� ����������� �������������, ��������:

     {\rm level}_{i+1}[w] \ge {\rm level}_i[w] + 2.

    ������ �� ����� ��������� �� �� ����� ����������� �� ����� ����������� ���� �� v (�.�. ��� ������ ��������������� ����� ��������� � \rm level ��� ������� ���), � � ����� ������� ��������� �����������.

����� 2. ���������� ����� ������� � ������ ������ ������������� ����� ������ ���� ���������, �.�.:

 {\rm level}^\prime[t] > {\rm level}[t],

��� ������� �������� ��������, ���������� �� ��������� ���� ���������.

��������������: �� ����������. �����������, ��� ����� ���������� ������� ���� ���������, ���  {\rm level}^\prime[t] = {\rm level}[t] . ���������� ���������� ���� �� ������ � ����; �� �������������, ��� ����� ������ ����������� ����������. ������ ���������� ���� �� ��������� ���� �������� ������ ���� ���������� ���� ����� ����������� ������� ����, ���� �������� � ���. ����� �������, ������ � ������������: ������� s-t ����, ������� �� �������� ���������� ����, � ����� �� �� �����, ��� � ���������� ����. ���� ���� ������ ��� ���� "������������" ����������� �������, ���� �� ���������, � ��� � ����������� ������������, ��� � ����������� ��������.

��� ����� ���������� ����� �������� ��������� �������: �� i-�� ���� �������� ������ �������� � �������� ��� s-t ���� ����� i.

��������� ����� ����������� ���� �� s � t �� ����� ������������ n-1, ��, �������������, �������� ������ ��������� �� ����� n-1 ����.

����� ������������ ������

����� ��������� ���������� ��������� ������, ���� ������� �������� ���������� ������������ ������ � �������� ���� — �������� ����� ���������.

�� ���������� ��� ��������� �������� ���������� ������ ������������ ������:

  • ������ s-t ���� �� ������, ���� ����� ���� ���������. ���� ����� ����� �� O(m) ������� � �������, � ����� ����� ����� ����� O(m) (��������� ������ ���� �������� ��� ������� ���� �����). �������� ����������� ������ ������ ������������ ������ �������� O(m^2).

  • ���������� ���������� ����, ������ ������� � �������� ������ � ������� �� ����� ��� "������" ����, �.�. ����, ����� ������� �� ��������� ����� �� �����.

    ��� ����� ����� �����������: ���������� ������� ����� ����� ����, ��� �� ����������� ��� � ������ � ������� (����� ���� ������, ����� �� ������ ����� ����� � ����� ���� �� �����). � ����� ������ ����������, ���� ������ ������������ � ������ ��������� ������ ������� ��������� �� ������ ���������� �����, � ����������� ���� ������� � ����� ������ ������ � �������.

    ������ ����������� ����� �������. ������ ����� � ������� ����������� ���� ���������� ��� ������� ������ ����� (���� ���� ����� ������ �����), ���� ������������ ����� ��� ������� ������ ��������� (� ��������� ������). ����� ������, ��� ���� ������ ������ � ������� �� �������� ��������� �������� �� O (k + n), ��� k — ����� ����������� ����������. ��������, ��� ����� �������� ������ � ������� � ������ ������ ������ ������������ ������ ����� O (p), ��� p — ����� ����, ���������� ���� ����������� �������, �� ���� �������� ������ ������������ ������ ���������� �� O (p k + p n), ���, ��������, ��� ��� ��������� � ����� ������ ���������� O (m), ��� ����������� O (m + pn). � ������ ������, ����� ����������� ����� �������� ��� ����, ����������� ���������� O (n m); ��� ����������� � ����� �������������� �����.

    ����� �������, ��� ���� ������ ���������� ������������ ������ ����������� ���������� � ��� ������, ��� �� ����� ������ �������������� ���� �� ������ O (n) �������� � �������. ������ � ���� � ������� �������� �� ����� ������� �������������� ��������� ������ � ��������-����� (������� ���� ���� ������������� ���� �� O (m)).

    ���� ������ ������� �������� ��-�������� ������� ��� ����������, �� ���������� �����������, � ������ �������� ����� ����������� �� ��������.

  • ����� ��������� ����������� ��������� ������ — ������������ ������� ������� (Sleator) � ������� (Tarjan)). ����� ������ ����������� ����� ����� ����� �� ����� O (m \log n).

�����������

����� �������, ���� �������� ������ ����������� �� O (n^2 m), ���� ����������� ����� ������ ��������� ���� �������� �� O (n m). ���������� � �������������� ������������ �������� ������� � ������� ����� �������� �� ����� O (n m \log n).

��������� ����

��������� ����� ("unit network") ���������� ����� ����, � ������� ���������� ����������� ���� ������������ ���� ����� �������, � � ����� �������, ����� ������ � �����, ���� ��������, ���� ��������� ����� �����������.

���� ������ �������� ���������� ������, ��������� � ������ ������ ������������� ������������� ����������� ���� �������� ������ ���������.

�������, ��� �� ��������� ����� �������� ������ ���� � ������� ���������� (������� �� ������������ ������ ������������ �� O (n^2 m)) �������� �� ����� O (m \sqrt{n}), �������� �� ������ ������ ����������� ������������� ���� �� ������ ��������� ���������� — �������� ���������-�����.

��-������, �������, ��� ���������� ���� �������� ������ ������������ ������, ������� �� ������������ ����� �������� �� ����� O (n m), � ����� � ���������� ����������� ������������� ����� �������� �� O (m): � ���� ����, ��� ������ ����� �� ����� ����������� ����� ������ ����.

��-������, ������ ����� ���������� ���, ������� ����� ��������� � ������ ��������� �����.

����� ��� ���� ����������� \sqrt{n} ��� ��������� ������; ����� ��� ������������� ���� ����� �� ����� \sqrt{n} ��� ����������. ����� f — ������� ��������� �����, � f^* — ������� ������������ �����; ���������� �� ��������: f^* - f. ��� ������������ �� ���� ����� � ���������� ���� G^R. ���� ����� ����� �������� |f^*| - |f|, � ����� ������� ����� ����� ���� ��� �������. ��� ����� ��������������� �� ����� �� |f^*| - |f| ����� �� s � t �, ��������, ������. ��������� ���� ��������, �� ��� ��� ���� �� ����� ����� ����� ������, �������, �������� �������������, ��������� ���������� ������ � ��� cnt ����� ������� ���:

 cnt \ge (|f^*| - |f|) \cdot \sqrt{n}.

� ������ �������, ��������, ��� cnt \le n, �� �������� ������:

 |f^*| - |f| \le \sqrt{n},

��� ��������, ��� ��� ����� \sqrt{n} ��� ��������� ������ �������������� ������� ������������ �����.

�������������, ����� ����� ��� ��������� ������, ����������� �� ��������� �����, ����� ������� ��� 2 \sqrt{n}, ��� � ����������� ��������.

����������

������� ��� ���������� ��������� �� O (n^2 m), ���������� �� �����, �������� ��������� ��������� � �������� ��������� ��������������.

���������� ��� ������� � ���� ������ ���������

const int MAXN = ...; // ����� ������
const int INF = 1000000000; // ���������-�������������
 
int n, c[MAXN][MAXN], f[MAXN][MAXN], s, t, d[MAXN], ptr[MAXN], q[MAXN];
 
bool bfs() {
	int qh=0, qt=0;
	q[qt++] = s;
	memset (d, -1, n * sizeof d[0]);
	d[s] = 0;
	while (qh < qt) {
		int v = q[qh++];
		for (int to=0; to<n; ++to)
			if (d[to] == -1 && f[v][to] < c[v][to]) {
				q[qt++] = to;
				d[to] = d[v] + 1;
			}
	}
	return d[t] != -1;
}
 
int dfs (int v, int flow) {
	if (!flow)  return 0;
	if (v == t)  return flow;
	for (int & to=ptr[v]; to<n; ++to) {
		if (d[to] != d[v] + 1)  continue;
		int pushed = dfs (to, min (flow, c[v][to] - f[v][to]));
		if (pushed) {
			f[v][to] += pushed;
			f[to][v] -= pushed;
			return pushed;
		}
	}
	return 0;
}
 
int dinic() {
	int flow = 0;
	for (;;) {
		if (!bfs())  break;
		memset (ptr, 0, n * sizeof ptr[0]);
		while (int pushed = dfs (s, INF))
			flow += pushed;
	}
	return flow;
}

���� ������ ���� �������������� �������: ������ ���� ������ ���������� n, s, t, � ����� ������� ������� ���������� ������������ c[][]. �������� ������� ������� — \rm dinic(), ������� ���������� �������� ���������� ������������� ������.

���������� ��� ������� � ���� ������� ���������

const int MAXN = ...; // ����� ������
const int INF = 1000000000; // ���������-�������������
 
struct edge {
	int a, b, cap, flow;
};
 
int n, s, t, d[MAXN], ptr[MAXN], q[MAXN];
vector<edge> e;
vector<int> g[MAXN];
 
void add_edge (int a, int b, int cap) {
	edge e1 = { a, b, cap, 0 };
	edge e2 = { b, a, 0, 0 };
	g[a].push_back ((int) e.size());
	e.push_back (e1);
	g[b].push_back ((int) e.size());
	e.push_back (e2);
}
 
bool bfs() {
	int qh=0, qt=0;
	q[qt++] = s;
	memset (d, -1, n * sizeof d[0]);
	d[s] = 0;
	while (qh < qt && d[t] == -1) {
		int v = q[qh++];
		for (size_t i=0; i<g[v].size(); ++i) {
			int id = g[v][i],
				to = e[id].b;
			if (d[to] == -1 && e[id].flow < e[id].cap) {
				q[qt++] = to;
				d[to] = d[v] + 1;
			}
		}
	}
	return d[t] != -1;
}
 
int dfs (int v, int flow) {
	if (!flow)  return 0;
	if (v == t)  return flow;
	for (; ptr[v]<(int)g[v].size(); ++ptr[v]) {
		int id = g[v][ptr[v]],
			to = e[id].b;
		if (d[to] != d[v] + 1)  continue;
		int pushed = dfs (to, min (flow, e[id].cap - e[id].flow));
		if (pushed) {
			e[id].flow += pushed;
			e[id^1].flow -= pushed;
			return pushed;
		}
	}
	return 0;
}
 
int dinic() {
	int flow = 0;
	for (;;) {
		if (!bfs())  break;
		memset (ptr, 0, n * sizeof ptr[0]);
		while (int pushed = dfs (s, INF))
			flow += pushed;
	}
	return flow;
}

���� ������ ���� �������������� �������: ������ ���� ������ ���������� n, s, t, � ����� ��������� ��� ���� (���������������) � ������� ������� ������� \rm add\_edge. �������� ������� ������� — \rm dinic(), ������� ���������� �������� ���������� ������������� ������.