최대 흐름 - MPM 알고리즘¶
MPM(Malhotra, Pramodh-Kumar, Maheshwari) 알고리즘은 최대 흐름 문제를 $O(V^3)$에 해결합니다. 이 알고리즘은 Dinic 알고리즘과 유사합니다.
알고리즘¶
Dinic 알고리즘과 마찬가지로 MPM은 단계별로 실행되며, 각 단계에서는 $G$의 잔여 네트워크로 만든 계층 네트워크에서 차단 흐름을 찾습니다. Dinic 알고리즘과의 주된 차이점은 차단 흐름을 찾는 방법입니다. 계층 네트워크 $L$을 생각해 봅시다. 각 노드에 대해 내부 퍼텐셜과 외부 퍼텐셜을 다음과 같이 정의합니다:
또한 $p_{in}(s) = p_{out}(t) = \infty$로 둡니다. $p_{in}$과 $p_{out}$이 주어지면 포텐셜을 $p(v) = min(p_{in}(v), p_{out}(v))$로 정의합니다. $p(r) = min\{p(v)\}$이면 노드 $r$을 기준 노드라고 부릅니다. 기준 노드 $r$을 생각해 봅시다. $p(r)$이 $0$이 되도록 흐름을 $p(r)$만큼 증가시킬 수 있다고 주장합니다. 이것이 참인 이유는 $L$이 비순환이기 때문입니다. 따라서 $r$에서 나가는 간선을 통해 흐름을 밀어낼 수 있으며, 흐름이 각 노드에 도달했을 때 그 노드에는 흐름을 밀어낼 만큼의 외부 퍼텐셜이 충분하므로 흐름은 $t$에 도달합니다. 마찬가지로 $s$로부터 흐름을 끌어올 수 있습니다. 블로킹 흐름의 구성은 이 사실에 기반합니다. 각 반복에서 기준 노드를 찾고, $r$을 거쳐 $s$에서 $t$로 흐름을 밀어냅니다. 이 과정은 BFS로 시뮬레이션할 수 있습니다. 완전히 포화된 간선은 어차피 이 단계에서 이후에 사용되지 않으므로 모두 $L$에서 삭제할 수 있습니다. 마찬가지로, $s$와 $t$가 아니면서 나가는 호나 들어오는 호가 없는 모든 노드는 삭제할 수 있습니다.
반복은 최대 $V$번이고(적어도 선택된 기준 노드는 삭제되기 때문입니다), 각 반복에서 지나간 간선 중 최대 $V$개를 제외한 모든 간선을 삭제하므로 각 단계는 $O(V^2)$에 동작합니다. 이를 합하면 $O(V^2 + E) = O(V^2)$를 얻습니다. 단계는 $V$개 미만이므로(여기의 증명을 참고하십시오), MPM은 전체적으로 $O(V^3)$에 동작합니다.
구현¶
struct MPM{
struct FlowEdge{
int v, u;
long long cap, flow;
FlowEdge(){}
FlowEdge(int _v, int _u, long long _cap, long long _flow)
: v(_v), u(_u), cap(_cap), flow(_flow){}
FlowEdge(int _v, int _u, long long _cap)
: v(_v), u(_u), cap(_cap), flow(0ll){}
};
const long long flow_inf = 1e18;
vector<FlowEdge> edges;
vector<char> alive;
vector<long long> pin, pout;
vector<list<int> > in, out;
vector<vector<int> > adj;
vector<long long> ex;
int n, m = 0;
int s, t;
vector<int> level;
vector<int> q;
int qh, qt;
void resize(int _n){
n = _n;
ex.resize(n);
q.resize(n);
pin.resize(n);
pout.resize(n);
adj.resize(n);
level.resize(n);
in.resize(n);
out.resize(n);
}
MPM(){}
MPM(int _n, int _s, int _t){resize(_n); s = _s; t = _t;}
void add_edge(int v, int u, long long cap){
edges.push_back(FlowEdge(v, u, cap));
edges.push_back(FlowEdge(u, v, 0));
adj[v].push_back(m);
adj[u].push_back(m + 1);
m += 2;
}
bool bfs(){
while(qh < qt){
int v = q[qh++];
for(int id : adj[v]){
if(edges[id].cap - edges[id].flow < 1)continue;
if(level[edges[id].u] != -1)continue;
level[edges[id].u] = level[v] + 1;
q[qt++] = edges[id].u;
}
}
return level[t] != -1;
}
long long pot(int v){
return min(pin[v], pout[v]);
}
void remove_node(int v){
for(int i : in[v]){
int u = edges[i].v;
auto it = find(out[u].begin(), out[u].end(), i);
out[u].erase(it);
pout[u] -= edges[i].cap - edges[i].flow;
}
for(int i : out[v]){
int u = edges[i].u;
auto it = find(in[u].begin(), in[u].end(), i);
in[u].erase(it);
pin[u] -= edges[i].cap - edges[i].flow;
}
}
void push(int from, int to, long long f, bool forw){
qh = qt = 0;
ex.assign(n, 0);
ex[from] = f;
q[qt++] = from;
while(qh < qt){
int v = q[qh++];
if(v == to)
break;
long long must = ex[v];
auto it = forw ? out[v].begin() : in[v].begin();
while(true){
int u = forw ? edges[*it].u : edges[*it].v;
long long pushed = min(must, edges[*it].cap - edges[*it].flow);
if(pushed == 0)break;
if(forw){
pout[v] -= pushed;
pin[u] -= pushed;
}
else{
pin[v] -= pushed;
pout[u] -= pushed;
}
if(ex[u] == 0)
q[qt++] = u;
ex[u] += pushed;
edges[*it].flow += pushed;
edges[(*it)^1].flow -= pushed;
must -= pushed;
if(edges[*it].cap - edges[*it].flow == 0){
auto jt = it;
++jt;
if(forw){
in[u].erase(find(in[u].begin(), in[u].end(), *it));
out[v].erase(it);
}
else{
out[u].erase(find(out[u].begin(), out[u].end(), *it));
in[v].erase(it);
}
it = jt;
}
else break;
if(!must)break;
}
}
}
long long flow(){
long long ans = 0;
while(true){
pin.assign(n, 0);
pout.assign(n, 0);
level.assign(n, -1);
alive.assign(n, true);
level[s] = 0;
qh = 0; qt = 1;
q[0] = s;
if(!bfs())
break;
for(int i = 0; i < n; i++){
out[i].clear();
in[i].clear();
}
for(int i = 0; i < m; i++){
if(edges[i].cap - edges[i].flow == 0)
continue;
int v = edges[i].v, u = edges[i].u;
if(level[v] + 1 == level[u] && (level[u] < level[t] || u == t)){
in[u].push_back(i);
out[v].push_back(i);
pin[u] += edges[i].cap - edges[i].flow;
pout[v] += edges[i].cap - edges[i].flow;
}
}
pin[s] = pout[t] = flow_inf;
while(true){
int v = -1;
for(int i = 0; i < n; i++){
if(!alive[i])continue;
if(v == -1 || pot(i) < pot(v))
v = i;
}
if(v == -1)
break;
if(pot(v) == 0){
alive[v] = false;
remove_node(v);
continue;
}
long long f = pot(v);
ans += f;
push(v, s, f, false);
push(v, t, f, true);
alive[v] = false;
remove_node(v);
}
}
return ans;
}
};