Dinic 알고리즘은 유량이 흐르는 그래프에서 s에서 e로 흘릴 수 있는 최대 유량을 찾는 알고리즘으로,
단순하게 구현할 경우 
의 복잡도를 가집니다.
이 문제에서 차단 유량을 찾을 때 Link/Cut Tree를 이용하면 차단 유량을 
에 찾을 수 있고,
알고리즘 전체는 
가 됩니다.
차단 유량을 찾는 방법에 대해서만 설명하겠습니다.
Link/Cut Tree에 구현되어 있어야 하는 기능
-경로에서 비용이 최소인 간선(비용이 같으면 루트에 가까운 간선)
-경로의 모든 간선에 비용을 더함
-노드가 포함된 트리의 루트를 찾음
-노드의 부모 노드를 찾음
Step 1) 흐를 수 있는 유량을 찾는 Step : findBlockFlow()
x = root(s)
if (x == e) Step 3로
y = x에서 y로 유량이 흐를 수 있는 노드
if (y == null) {
if (x == s) Step 5로
else Step 4로
}
x를 y의 아래 붙이고, 간선의 비용을 흐를 수 있는 유량으로 한다
Step 1을 반복한다
Step 2) 유량이 흐를 수 없는 간선 (x, y = parent(x))를 제거하는 Step : removeEdge(node * x)
x->y의 남은 유량을 y->x의 남은 유량으로 모두 바꾼다
트리에서 (x, y)를 제거한다
s와 x 사이의 경로에 비용이 0인 간선이 있다면 해당 간선에서 Step 2)를 반복한다
없다면 Step 1)으로 돌아간다
Step 3) 차단 유량을 찾았을 때 갱신시키는 Step : updateFlow()
e = (x, parent(x)) = s와 e 사이의 경로에 있는 간선 가중치가 최소인 간선
w = e의 가중치
답에 w를 더한다
s와 e 사이의 경로에 -w를 더한다
Step 2)로 가서 e를 지운다
Step 4) 더 이상 유량을 흘릴 수 없는 정점 x를 제거하는 Step : removeVertex(node * x)
x의 역 간선에 연결된 정점 y들을 보면서 parent(y) == x일 경우 x와 y를 끊는다
Step 5) 남은 트리의 간선들을 갱신시키는 Step : initTree()
모든 정점 x들을 보면서 x가 루트가 아닐 경우 (x, parent(x))의 가중치를 보고 흐를 수 있는 유량을 갱신한다.
차단 유량을 모두 찾았으므로 종료한다
코드 보기
struct flow {
node * x;
int w; //Vertex, Weight
flow(node * x, int w) : x(x), w(w) {}
bool operator<(const flow &f) const {
return x->index < f.x->index;
}
};
vector<flow> edge[N + 1];
int edgeIndex[N + 1];
int level[N + 1];
bool removed[N + 1];
node * tree[N + 1];
int findBlockFlow();
void removeEdge(node *);
int updateFlow();
void removeVertex(node *);
void initTree();
int findBlockFlow() { //Step 1
int flows = 0;
while (true) {
node * x = root(s);
if (s == e) {
flows += updateFlow();
continue;
}
for (; edgeIndex[x->index] < edge[x->index].size(); ++edgeIndex[x->index]) {
if (level[x->index] + 1 == level[edge[x->index][edgeIndex[x->index]].x->index]
&& !removed[edge[x->index][edgeIndex[x->index]].x->index]
&& edge[x->index][edgeIndex[x->index]].w > 0) {
link(x, tree[edge[x->index][edgeIndex[x->index]].x->index]);
access(x);
x->value = edge[x->index][edgeIndex[x->index]].w;
update(x);
break;
}
}
if (edgeIndex[x->index] == edge[x->index].size()) {
if (x == s) break;
removeVertex(x);
}
else ++edgeIndex[x->index];
}
initTree();
return flows;
}
void removeEdge(node * x) { //Step 2
while (true) {
access(x);
x->value = INT_MAX;
update(x);
node * p = parent(x);
cut(x);
auto e1 = lower_bound(edge[x->index].begin(), edge[x->index].end(), flow(p, -1));
auto e2 = lower_bound(edge[p->index].begin(), edge[p->index].end(), flow(x, -1));
e2->w += e1->w;
e1->w = 0;
access(s);
if (s->minValue > 0) break;
x = s->minNode;
}
}
int updateFlow() { //Step 3
access(s);
int value = s->minValue;
s->lazyAdd = -value;
s->minValue -= value;
s->value -= value;
removeEdge(s->minNode);
return value;
}
void removeEdge(node * x) { //Step 4
removed[x->index] = true;
for (flow &i : edge[x->index]) {
node * p = parent(i.x);
if (p != x) continue;
access(i.x);
int value = i.x->value;
i.x->value = INT_MAX;
cut(i.x);
auto e = lower_bound(edge[i.x->index].begin(), edge[i.x->index].end(), flow(x, -1));
i.w += e->w - value;
e->w = value;
}
}
void initTree() { //Step 5
for (int i = 1; i <= N; ++i) {
node * p = parent(tree[i]);
if (p == NULL) continue;
access(tree[i]);
int value = tree[i]->value;
auto e1 = lower_bound(edge[i].begin(), edge[i].end(), flow(p, -1));
auto e2 = lower_bound(edge[p->index].begin(), edge[p->index].end(), flow(tree[i], -1));
e2->w += e1->w - value;
e1->w = value;
}
}
모든 간선들과 정점들은 
시간만큼 관여한다.
따라서 복잡도는 
가 걸린다.
답글 남기기