Перелёты

@1timchik1 · Регистрация: 27.06.2020

Студворк — интернет-сервис помощи студентам

Не могу понять, почему программа не проходит по времени с асимптотикой O(n^3) при ограничении n <= 1000 и тайм лимиту в 1,5 с
При разработке нового самолёта для внутренних авиалиний Байтландии возник вопрос, какого размера делать ёмкости для топлива. Для этого для каждой пары городов была собрана информация по расходу топлива на перелёт между этими городами. При этом на перелёт из A в B и из B в A может быть затрачено разное количество топлива.

Требуется вычислить минимально возможный объём топливных баков, при котором самолёт сможет (возможно, c промежуточными посадками для дозаправки в других городах) проделать путешествие между любыми двумя городами Байтландии.

Формат ввода
В первой строке задано одно целое число n (1 ≤ n ≤ 1000) — число городов в Байтландии.

Каждая из последующих n строк содержит по n целых чисел. a_ij (j-ое число в i-ой строке) равно расходу топлива при перелёте из i-ого города в j-ый (0 ≤ a_ij < 10⁹, a_ii=0 для всех i).

Формат вывода
Выведите одно целое число — ответ к задаче.
Ввод
4
0 10 12 16
11 0 8 9
10 13 0 22
13 10 17 0

Вывод
10

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int n;
    cin >> n;
 
    vector<vector<int>> gr(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> gr[i][j];
        }
    }
    
    int ans = -1e9;
    for (int k = 0; k < n; k++) {
        ans = -1e9;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                gr[i][j] = min(gr[i][j], max(gr[i][k], gr[k][j]));
                ans = max(ans, gr[i][j]);
            }
        }
    }
    cout << ans;
}

@yMHiy yoz · 31.05.2022, 21:25

Алгоритм сам по себе не рабочий.
Чё мы делаем?
Перебираем пути из i в j и смотрим не лучше ли нам полететь через k. А если лучше полететь через k и m?

Дейкстру осваивайте. За n^2 все кратчайшие пути из вершины A.

@QueryMonkey · 31.05.2022, 21:44

yMHiy yoz, это по прежнему О(n³) для рассчёта баков, так?

@Shamil1 · 01.06.2022, 11:35

Есть множество рёбер.
Сортируем их в порядке убывания веса. То есть, помещаем в Кучу (Пирамиду) за O(N logN).

Берём из Кучи по одному и проверяем, есть ли альтернативный более короткий путь.
Если нет, то это ответ.
Если да, то берём следующее ребро.

@QueryMonkey · 01.06.2022, 16:57

Сообщение от Shamil1

Есть множество рёбер.
Сортируем их в порядке убывания веса. То есть, помещаем в Кучу (Пирамиду) за O(N logN).

Берём из Кучи по одному

Цель сортировки непонятна. Если потом все равно перебираем все по одному.

Сообщение от Shamil1

и проверяем, есть ли альтернативный более короткий путь.
Если нет, то это ответ.

Ответ к задаче? Или ответ к паре точек? У нас О(n²) пар.

Непонятно как "проверяем" на полном графе между любыми двумя точками существует О(n!) путей без циклов.

Я совсем не понял ваше решение.

@Shamil1 · 01.06.2022, 17:18

Сообщение от QueryMonkey

Цель сортировки непонятна. Если потом все равно перебираем все по одному.

Берём максимальный элемент.
https://ru.wikipedia.org/wiki/... 1%87%D0%B0

Сообщение от QueryMonkey

Ответ к задаче? Или ответ к паре точек? У нас О(n²) пар.

Ответ к задаче. Нам нужно найти максимальный перелёт.

Сообщение от QueryMonkey

Непонятно как "проверяем" на полном графе между любыми двумя точками существует О(n!) путей без циклов.

Поиск кратчайшего пути между началом и концом ребра алгоритмом Дейкстры.

Добавлено через 14 минут
з.ы. Так как мы в Кучу не докладываем, то можно использовать отсортированный список.

@QueryMonkey · 01.06.2022, 18:29

Shamil1, теперь понял, спасибо.

Добавлено через 19 минут
Вижу подвох. Дейкстра находит кратчайший путь, но нас интересует путь с кратчайшим максимальным сегментом.

Например: А->Б:2, но а-в-г-д-б по одному хотя весь путь 4.
Это значит мне нужен бак размера 1, тк разрешено заправляться в каждом городе.

Ваш алгоритм даёт 2.

Добавлено через 13 минут
1timchik1, считаете минимум для каждой строки и для каждого столбца (исключая ноль-себя)

Максимальное из этих 2N чисел - ответ к задаче. Время О(N²), память О(1).

@Shamil1 · 01.06.2022, 18:39

Сообщение от QueryMonkey

Вижу подвох. Дейкстра находит кратчайший путь, но нас интересует путь с кратчайшим максимальным сегментом.

Согласен, подвох есть.
На самом деле нас интересует любой путь, не использующий текущее ребро. Можно использовать обход в ширину.

@Shamil1 · 01.06.2022, 18:56

QueryMonkey,
Но в результате получатется тот же n³, так как у нас n² рёбер. Только появляются дополнительные условия выхода из циклов.

@QueryMonkey · 01.06.2022, 19:53

Shamil1,

Ну как же, см выше (копирую для удобства читателя):

1timchik1, считаете минимум для каждой строки и для каждого столбца (исключая ноль-себя)

Максимальное из этих 2N чисел - ответ к задаче. Время О(N²), память О(1).

Задача проще чем та, над которой трудился Дейкстра.

Добавлено через 1 минуту
Столбцы и строки относятся к матрице в первом сообщении темы.

Добавлено через 40 минут
В коде моя идея выглядит примерно так:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
 
#define NODES   4
 
int aa[NODES][NODES] = 
{
  { 0, 10, 12, 16},
  {11,  0,  8,  9},
  {10, 13,  0, 22},
  {13, 10, 17,  0}
};
 
int main()
{
  int x = 0; // result
 
  for( int i = 0 ; i < NODES ; ++i )
  {
    unsigned r = ~0, c = ~0;
    for( int j = 0 ; j < NODES ; ++j )
      if( j != i )
      {
        if( aa[i][j] < r ) r = aa[i][j];
        if( aa[j][i] < c ) c = aa[j][i];
      }
    if( r > x ) x = r;
    if( c > x ) x = c;
  }
  printf( "%d\n", x );
}

Новые блоги и статьи Все статьи Все блоги /
Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.

@yMHiy yoz Заблокирован
	31.05.2022, 21:25
	Алгоритм сам по себе не рабочий. Чё мы делаем? Перебираем пути из i в j и смотрим не лучше ли нам полететь через k. А если лучше полететь через k и m? Дейкстру осваивайте. За n^2 все кратчайшие пути из вершины A. 0

@QueryMonkey Нарушающий 417 / 305 / 46 Регистрация: 13.04.2022 Сообщений: 1,759
	31.05.2022, 21:44
	yMHiy yoz, это по прежнему О(n³) для рассчёта баков, так? 0

@Shamil1 Модератор 3137 / 2284 / 469 Регистрация: 26.03.2015 Сообщений: 8,888
	01.06.2022, 11:35
	Есть множество рёбер. Сортируем их в порядке убывания веса. То есть, помещаем в Кучу (Пирамиду) за O(N logN). Берём из Кучи по одному и проверяем, есть ли альтернативный более короткий путь. Если нет, то это ответ. Если да, то берём следующее ребро. 0

@QueryMonkey Нарушающий 417 / 305 / 46 Регистрация: 13.04.2022 Сообщений: 1,759
	01.06.2022, 18:29
	Shamil1, теперь понял, спасибо. Добавлено через 19 минут Вижу подвох. Дейкстра находит кратчайший путь, но нас интересует путь с кратчайшим максимальным сегментом. Например: А->Б:2, но а-в-г-д-б по одному хотя весь путь 4. Это значит мне нужен бак размера 1, тк разрешено заправляться в каждом городе. Ваш алгоритм даёт 2. Добавлено через 13 минут 1timchik1, считаете минимум для каждой строки и для каждого столбца (исключая ноль-себя) Максимальное из этих 2N чисел - ответ к задаче. Время О(N²), память О(1). 0

@Shamil1 Модератор 3137 / 2284 / 469 Регистрация: 26.03.2015 Сообщений: 8,888
	01.06.2022, 18:56
	QueryMonkey, Но в результате получатется тот же n³, так как у нас n² рёбер. Только появляются дополнительные условия выхода из циклов. 0

Опции темы