Хамгийн их урсгал - MPM алгоритм¶
MPM (Малхотра, Прамод-Кумар ба Махешвари) алгоритм хамгийн их урсгалын бодлогыг $O(V^3)$-д бодно. Энэ алгоритм Диникийн алгоритм-тай төстэй.
Алгоритм¶
Диникийн алгоритмын нэгэн адил MPM фазуудаар ажиллах ба фаз бүрийн явцад бид $G$-ийн үлдэгдэл сүлжээний давхаргат сүлжээнд хаагч урсгалыг олно. Диникийнхээс гол ялгаа нь бид хаагч урсгалыг хэрхэн олох явдал юм. Давхаргат сүлжээ $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$-ээс урсгалыг татаж чадна. Хаагч урсгалыг байгуулах нь энэ баримт дээр суурилна. Итерац бүрд бид лавлах зангилааг олж, урсгалыг $s$-ээс $t$ рүү $r$-ээр дамжуулан түлхэнэ. Энэ процессыг BFS-ээр загварчилж болно. Бүрэн ханасан бүх нумыг $L$-ээс устгаж болно, учир нь тэдгээр нь энэ фазад цаашид ямар ч байсан ашиглагдахгүй. Үүний нэгэн адил гарах эсвэл орох нумгүй, $s$ ба $t$-ээс өөр бүх зангилааг устгаж болно.
Фаз бүр $O(V^2)$-д ажиллана, учир нь хамгийн ихдээ $V$ итерац байх ба (учир нь дор хаяж сонгосон лавлах зангилаа устгагдана) итерац бүрд бид дайрч өнгөрсөн бүх ирмэгээс хамгийн ихдээ $V$-ээс бусдыг устгана. Нийлбэрлэвэл бид $O(V^2 + E) = O(V^2)$ авна. $V$-ээс цөөн фаз байдаг тул (эндээс баталгааг үз) MPM нийтдээ $O(V^3)$-д ажиллана.
Implementation¶
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;
}
};