Хоёр дахь хамгийн бага тэлэх мод¶
Хамгийн бага тэлэх мод $T$ гэдэг нь өгөгдсөн граф $G$-ийн бүх оройг хамарсан, боломжит бүх тэлэх модны дотроос бүх ирмэгийн жингийн нийлбэр хамгийн бага байх мод юм. Хоёр дахь хамгийн бага MST $T'$ гэдэг нь граф $G$-ийн боломжит бүх тэлэх модны дотроос бүх ирмэгийн жингийн нийлбэр хоёр дахь хамгийн бага байх тэлэх мод юм.
Ажиглалт¶
$T$ нь граф $G$-ийн хамгийн бага тэлэх мод байг. Хоёр дахь хамгийн бага тэлэх мод нь $T$-ээс ердөө нэг ирмэгийн солилтоор ялгаатай болохыг ажиглаж болно. (Энэ мэдэгдлийн баталгааг эндээс 23-1 бодлогоос үз).
Тиймээс бид $T$-д байхгүй ирмэг $e_{new}$-г олж, түүнийг $T$ дэх ирмэгээр (тэр нь $e_{old}$ байг) солих хэрэгтэй бөгөөд ингэхдээ шинэ граф $T' = (T \cup \{e_{new}\}) \setminus \{e_{old}\}$ нь тэлэх мод байх ба жингийн зөрүү ($e_{new} - e_{old}$) хамгийн бага байх ёстой.
Крускалын алгоритм ашиглах¶
Бид эхлээд MST олохын тулд Крускалын алгоритм ашиглаж, дараа нь түүнээс ганц ирмэг хасаж, өөр ирмэгээр солихыг оролдож болно.
- Ирмэгүүдийг $O(E \log E)$-д эрэмбэлээд, дараа нь Крускал ашиглан $O(E)$-д MST ол.
- MST дэх ирмэг бүрийн хувьд (түүнд $V-1$ ирмэг байна) сонгогдож болохгүйн тулд түүнийг ирмэгийн жагсаалтаас түр хас.
- Дараа нь үлдсэн ирмэгүүдийг ашиглан $O(E)$-д MST-г дахин олохыг оролд.
- Үүнийг MST дэх бүх ирмэгийн хувьд хийж, бүгдийн хамгийн сайныг ав.
Тэмдэглэл: бид 3-р алхамд ирмэгүүдийг дахин эрэмбэлэх шаардлагагүй.
Тэгэхээр нийт time complexity нь $O(E \log V + E + V E)$ = $O(V E)$ болно.
Хамгийн бага нийтлэг өвгийн (LCA) бодлого болгон загварчлах¶
Өмнөх хандлагад бид MST-ийн нэг ирмэгийг хасах бүх боломжийг туршсан. Энд бид яг эсрэгээр нь хийнэ. Бид MST-д аль хэдийн байхгүй ирмэг бүрийг нэмэхийг оролдоно.
- Ирмэгүүдийг $O(E \log E)$-д эрэмбэлээд, дараа нь Крускал ашиглан $O(E)$-д MST ол.
- MST-д аль хэдийн байхгүй ирмэг $e$ бүрийн хувьд түүнийг MST-д түр нэмж цикл үүсгэ. Цикл нь LCA-гаар дайран өнгөрнө.
- Ирмэг $e$-ийн зангилаануудын эцгүүдийг LCA хүртэл дагаж, цикл дэх $e$-тэй тэнцүү биш хамгийн их жинтэй ирмэг $k$-г ол.
- $k$-г түр хасаж, шинэ тэлэх мод үүсгэ.
- Жингийн зөрүү $\delta = weight(e) - weight(k)$-г тооцоолж, өөрчлөгдсөн ирмэгийн хамт сана.
- Бусад бүх ирмэгийн хувьд 2-р алхмыг давтаж, MST-тэй жингийн зөрүү нь хамгийн бага байх тэлэх модыг буцаа.
Алгоритмын time complexity нь энэ алгоритмын 2-р алхам дахь хамгийн их жинтэй ирмэгүүд болох $k$-г бид хэрхэн тооцоолохоос хамаарна. Тэдгээрийг $O(E \log V)$-д үр ашигтай тооцоолох нэг арга бол бодлогыг Хамгийн бага нийтлэг өвгийн (LCA) бодлого болгон хувиргах явдал юм.
Бид MST-г үндэслэх замаар LCA-г урьдчилан боловсруулах ба мөн зангилаа бүрийн хувьд түүний өвгүүд хүрэх зам дээрх хамгийн их ирмэгийн жинг тооцоолно. Үүнийг LCA-д зориулсан Хоёртын өргөлт ашиглан хийж болно.
Энэ хандлагын эцсийн time complexity нь $O(E \log V)$ юм.
Жишээ нь:
*Зурагт зүүн талд нь MST, баруун талд нь хоёр дахь хамгийн бага MST байна.*
Өгөгдсөн графт бид MST-г дээд талын цэнхэр оройд үндэслээд, дараа нь MST-д байхгүй ирмэгүүдийг сонгож эхлэн алгоритмаа ажиллуулна гэж үзье. Хамгийн эхэнд сонгосон ирмэг нь 36 жинтэй ирмэг $(u, v)$ байг. Энэ ирмэгийг модонд нэмэхэд 36 - 7 - 2 - 34 цикл үүснэ.
Одоо бид $\text{LCA}(u, v) = p$-г олох замаар энэ цикл дэх хамгийн их жинтэй ирмэгийг олно. Бид $u$-ээс $p$ хүрэх ба $v$-ээс $p$ хүрэх зам дээрх хамгийн их жинтэй ирмэгийг тооцоолно. Тэмдэглэл: зарим тохиолдолд $\text{LCA}(u, v)$ нь $u$ эсвэл $v$-тэй тэнцүү байж бас болно. Энэ жишээнд бид цикл дэх хамгийн их ирмэгийн жин болгож 34 жинтэй ирмэгийг авна. Тэр ирмэгийг хасснаар бид жингийн зөрүү нь ердөө 2 байх шинэ тэлэх мод авна.
Үүнийг анхны MST-ийн хэсэг биш бусад бүх ирмэгийн хувьд ч хийсний дараа энэ тэлэх мод нь мөн нийтдээ хоёр дахь хамгийн сайн тэлэх мод байсныг бид харж болно. 14 жинтэй ирмэгийг сонгох нь модны жинг 7-оор нэмэгдүүлэх ба 27 жинтэй ирмэгийг сонгох нь 14-өөр, 28 жинтэй ирмэгийг сонгох нь 21-ээр, 39 жинтэй ирмэгийг сонгох нь модыг 5-аар нэмэгдүүлнэ.
Implementation¶
struct edge {
int s, e, w, id;
bool operator<(const struct edge& other) { return w < other.w; }
};
typedef struct edge Edge;
const int N = 2e5 + 5;
long long res = 0, ans = 1e18;
int n, m, a, b, w, id, l = 21;
vector<Edge> edges;
vector<int> h(N, 0), parent(N, -1), size(N, 0), present(N, 0);
vector<vector<pair<int, int>>> adj(N), dp(N, vector<pair<int, int>>(l));
vector<vector<int>> up(N, vector<int>(l, -1));
pair<int, int> combine(pair<int, int> a, pair<int, int> b) {
vector<int> v = {a.first, a.second, b.first, b.second};
int topTwo = -3, topOne = -2;
for (int c : v) {
if (c > topOne) {
topTwo = topOne;
topOne = c;
} else if (c > topTwo && c < topOne) {
topTwo = c;
}
}
return {topOne, topTwo};
}
void dfs(int u, int par, int d) {
h[u] = 1 + h[par];
up[u][0] = par;
dp[u][0] = {d, -1};
for (auto v : adj[u]) {
if (v.first != par) {
dfs(v.first, u, v.second);
}
}
}
pair<int, int> lca(int u, int v) {
pair<int, int> ans = {-2, -3};
if (h[u] < h[v]) {
swap(u, v);
}
for (int i = l - 1; i >= 0; i--) {
if (h[u] - h[v] >= (1 << i)) {
ans = combine(ans, dp[u][i]);
u = up[u][i];
}
}
if (u == v) {
return ans;
}
for (int i = l - 1; i >= 0; i--) {
if (up[u][i] != -1 && up[v][i] != -1 && up[u][i] != up[v][i]) {
ans = combine(ans, combine(dp[u][i], dp[v][i]));
u = up[u][i];
v = up[v][i];
}
}
ans = combine(ans, combine(dp[u][0], dp[v][0]));
return ans;
}
int main(void) {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
parent[i] = i;
size[i] = 1;
}
for (int i = 1; i <= m; i++) {
cin >> a >> b >> w; // 1-indexed
edges.push_back({a, b, w, i - 1});
}
sort(edges.begin(), edges.end());
for (int i = 0; i <= m - 1; i++) {
a = edges[i].s;
b = edges[i].e;
w = edges[i].w;
id = edges[i].id;
if (unite_set(a, b)) {
adj[a].emplace_back(b, w);
adj[b].emplace_back(a, w);
present[id] = 1;
res += w;
}
}
dfs(1, 0, 0);
for (int i = 1; i <= l - 1; i++) {
for (int j = 1; j <= n; ++j) {
if (up[j][i - 1] != -1) {
int v = up[j][i - 1];
up[j][i] = up[v][i - 1];
dp[j][i] = combine(dp[j][i - 1], dp[v][i - 1]);
}
}
}
for (int i = 0; i <= m - 1; i++) {
id = edges[i].id;
w = edges[i].w;
if (!present[id]) {
auto rem = lca(edges[i].s, edges[i].e);
if (rem.first != w) {
if (ans > res + w - rem.first) {
ans = res + w - rem.first;
}
} else if (rem.second != -1) {
if (ans > res + w - rem.second) {
ans = res + w - rem.second;
}
}
}
}
cout << ans << "\n";
return 0;
}
Эх сурвалж¶
- Competitive Programming-3, by Steven Halim
- web.mit.edu