Бретт Балансирующий Бот выполняет миссию по свержению человеческих повелителей своих друзей. В городе, состоящем из N зданий, они планируют атаки Q, где они крадутся через M электрических кабелей, соединяющих здания A_i и B_i с опасностью D_i. Они начнут с начального здания S_i и перейдут к конечному зданию E_i. Затем они пробираются в здание назначения и выбрасывают живущего в здании повелителя-человека в окно во имя прогресса (Защита прогресса).
Опасность пути определяется как наивысшее значение опасности для любого кабеля на этом пути. Бретт хотел бы свести к минимуму эту связанную опасность, поэтому для каждой атаки они хотели бы, чтобы вы, единственный человек, которому они доверяют, планировали каждый маршрут, сводя к минимуму максимальную опасность, с которой он сталкивается, и определяя максимальную опасность, с которой они столкнутся на каждом из Q маршруты. Наконец, чтобы успокоить их, прежде чем браться за эту опасную задачу, они хотели бы, чтобы вы вывели сумму уровней опасности всех кабелей, которые вы можете пообещать не использовать в любой возможной атаке в будущем.
Чтобы увидеть или попытаться решить проблему полностью, зарегистрируйтесь здесь, затем нажмите здесь.
Решение
Мы можем начать с упрощения постановки задачи. Нас просят найти серию путей с минимальной опасностью, учитывая серию начальных и конечных точек. Кроме того, нас просят вывести сумму общей предотвращенной опасности, сумму ребер, которые никогда не будут преодолены.
Чтобы решить первую проблему, как найти путь наименьшей опасности? Обратите внимание, что при максимальной опасности X от A до B и максимальной опасности Y от B до C, путь от A до C имеет максимальную опасность ≤ max (X, Y). Это связано с тем, что путь от A к C может проходить по тому же пути, что и путь от A к B, затем от B к C, и устранять некоторые повторяющиеся ребра. Если нам удастся создать связный подграф с минимальным максимальным весом ребра, то мы сможем маршрутизировать все пути в этом подграфе. Мы можем построить этот подграф, жадно выбирая наименее опасные ребра, которые соединяют две ранее разъединенные части, продолжая до тех пор, пока подграф не будет соединен. Затем мы можем использовать простой алгоритм поиска в глубину, чтобы найти путь с минимальной опасностью. Мы вернемся к этому позже.
Чтобы решить вторую проблему, мы неизбежно должны определить, какие опасности и, следовательно, какие грани никогда не пересекаются. Таким образом, мы также будем знать, какие края пройдены. Наше решение должно максимизировать сумму непроходимых ребер, минимизируя сумму пройденных ребер. Мы знаем, что для того, чтобы охватить все возможные пути, граф, представляющий наши пройденные ребра, должен быть соединен. Таким образом, нам нужно будет найти граф минимального веса для обхода, который охватывает больший граф, представляющий проблему. Граф размера N требует, чтобы было соединено N-1 ребер, и любой граф с N или более ребрами обязательно имеет схемы. Таким образом, мы знаем, что этот граф минимального веса должен иметь N-1 ребро, иначе мы могли бы удалить ребро внутри схемы, чтобы создать граф с меньшим весом. Таким образом, вторая половина просто просит нас найти минимальное связующее дерево (MST) и сумму весов не в этом MST.
Интересно, что решение первой половины фактически дает MST. Хотя он не позиционируется как MST, алгоритм, используемый для его решения, такой же, как Алгоритм Крускала, который используется для поиска MST. Несмотря на то, что задаются два вопроса, для решения этих двух проблем необходимо выполнить только одно основное вычисление, а именно, найти MST. Хотя Kruskal решает эту проблему, ее реализация может немного раздражать, поскольку определение того, какие части графа уже связаны, отнимает много времени. Зная, что наша конечная цель - найти MST, мы можем вместо этого использовать Алгоритм Прима, который постепенно строит MST, выбирая самую дешевую связь между незавершенным графом и несвязанной точкой и добавляя это ребро к граф, пока не будет сформировано остовное дерево.
Как только этот MST найден, вам нужно только найти минимальную опасность запрашиваемых путей и вывести общие неиспользованные веса.
Ниже мое решение на C ++.
// Solution by Bennett Liu
#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
using namespace std;
int n, m, q, a, b, d, s, e, avoided;
bool vis[1002];
pair<int, pair<int, int> > tmp;
vector<pair<int, pair<int, int> > > edges[1002];
vector<pair<int, int> > mst[1002];
priority_queue<pair<int, pair<int, int> > > pq;
int danger[1002][1002];
void dfs(int cur, int origin, int curDanger) {
danger[cur][origin] = curDanger;
danger[origin][cur] = curDanger;
vis[cur] = true;
for (int i = 0; i < mst[cur].size(); i++) {
if (!vis[mst[cur][i].second]) {
dfs(mst[cur][i].second, origin, max(curDanger, mst[cur][i].first));
}
}
return;
}
int main() {
// Get inputs
cin >> n >> m >> q;
for (int i = 0; i < m; i++) {
cin >> a >> b >> d;
edges[a].push_back(make_pair(-d, make_pair(a, b)));
edges[b].push_back(make_pair(-d, make_pair(b, a)));
}
// Build MST and calculate sum of avoided dangers
vis[1] = true;
for (int i = 0; i < edges[1].size(); i++) pq.push(edges[1][i]);
while (!pq.empty()) {
tmp = pq.top();
pq.pop();
if (vis[tmp.second.second]) avoided += (-tmp.first);
else {
avoided -= (-tmp.first);
vis[tmp.second.second] = true;
mst[tmp.second.first].push_back(make_pair((-tmp.first), tmp.second.second));
mst[tmp.second.second].push_back(make_pair((-tmp.first), tmp.second.first));
for (int i = 0; i < edges[tmp.second.second].size(); i++) pq.push(edges[tmp.second.second][i]);
}
}
// Precompute all dangers
for (int i = 1; i <= n; i++) {
// Reset vis array
for (int j = 1; j <= n; j++) vis[j] = false;
dfs(i, i, 0);
}
// Return precomputed dangers
for (int i = 0; i < q; i++) {
cin >> s >> e;
cout << danger[s][e] << endl;
}
cout << (avoided/2) << endl;
}
Я написал эту задачу для конкурса Girls Programming League 2018 с целью найти нетрадиционное применение для алгоритма MST.
