Задача "Pink Floyd"

@_Linkor_ · Регистрация: 14.06.2020

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

Всем доброго времени суток! Есть такая задача.
Группа Pink Floyd собирается дать новый концертный тур по всему миру. По предыдущему опыту группа знает, что солист Роджер Уотерс постоянно нервничает при перелетах. На некоторых маршрутах он теряет вес от волнения, а на других - много ест и набирает вес.
Известно, что чем больше весит Роджер, тем лучше выступает группа, поэтому требуется спланировать перелеты так, чтобы вес Роджера на каждом концерте был максимально возможным. Группа должна посещать города в том же порядке, в котором она дает концерты. При этом между концертами группа может посещать промежуточные города.
Входные данные
Первая строка входного файла содержит три натуральных числа n, m и k - количество городов в мире, количество рейсов и количество концертов, которые должна дать группа соответственно (n≤100, m≤10^4, 2≤k≤10^4). Города пронумерованы числами от 1 до n. Следующие m строк содержат описание рейсов, по одному на строке. Рейс номер i описывается тремя числами bi, ei и wi - номер начального и конечного города рейса и предполагаемое изменение веса Роджера в миллиграммах (1≤bi,ei≤n, −10^5≤wi≤10^5). Последняя строка содержит числа a1, a2, ..., ak - номера городов, в которых проводятся концерты. В начале концертного тура группа находится в городе a1.Гарантируется, что группа может дать все концерты.
Выходные данные
Первая строка выходного файла должна содержать число s - количество рейсов, которые должна сделать группа. Вторая строка должна содержать s чисел - номера используемых рейсов. Если существует такая последовательность маршрутов между концертами, что Роджер будет набирать вес неограниченно, то первая строка выходного файла должна содержать строку “infinitely kind”.
Примеры
входные данные
4 8 5
1 2 -2
2 3 3
3 4 -5
4 1 3
1 3 2
3 1 -2
3 2 -3
2 4 -10
1 3 1 2 4
выходные данные
6
5 6 5 7 2 3
входные данные
4 8 5
1 2 -2
2 3 3
3 4 -5
4 1 3
1 3 2
3 1 -2
3 2 -3
2 4 10
1 3 1 2 4
выходные данные
infinitely kind
Вот мой код к этой программе

Кликните здесь для просмотра всего текста

C++

#include <iostream>
#include <vector>
#include <map>
using namespace std;
int ret(vector<vector<int>>& from, int u, int v, vector<int>& path)
{
    if (u == v)
    {
        return 0;
    }
    if (from[u][v] == u || from[u][v] == v)
    {
        path.push_back(v);
        return 0;
    }
    ret(from, u, from[u][v], path);
    ret(from, from[u][v], v, path);
    return 0;
}
int main()
{
    const int inf = -1e9;
    bool cycle = false;
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> graph(n, vector<int>(n, inf)), from(n, vector<int>(n, -1));
    vector<int> a(k + 1, 0), path, ans;
    map<pair<int, int>, int> flights;
    path.push_back(0);
    for (int i = 0; i < m; i++)
    {
        int b, e, w;
        cin >> b >> e >> w;
        b--, e--;
        graph[b][e] = w;
        flights[{b, e}] = i;
        from[b][e] = b;
    }
    for (int i = 1; i <= k; i++)
    {
        cin >> a[i];
        a[i]--;
    }
    for (int i = 0; i < n; i++)
    {
        graph[i][i] = 0;
    }
    for (int K = 0; K < n; K++)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (graph[i][j] < graph[i][K] + graph[K][j])
                {
                    graph[i][j] = graph[i][K] + graph[K][j];
                    from[i][j] = K;
                }
            }
        }
    }
    for (int i = 0; i <= k; i++)
    {
        if (graph[a[i]][a[i]] > 0)
        {
            cycle = true;
        }
    }
    if (cycle)
    {
        cout << "infinitely kind";
    }
    else
    {
        for (int j = 1; j <= k; j++)
        {
            ret(from, a[j - 1], a[j], path);
        }
        for (int i = 1; i < path.size(); i++)
        {
            ans.push_back(flights[{path[i - 1], path[i]}] + 1);
        }
        cout << ans.size() << endl;
        for (auto el : ans)
        {
            cout << el << " ";
        }
    }
}

Но дело в том, что на информатиксе он проходит 11 тестов из 24. Помогите, пожалуйста, разобраться, где я допустил ошибку. Скорее всего, проблема таится где-то в функции

@LegionK · 17.11.2020, 23:37

Не ясно в каком порядке можно посещать города, в каком нельзя... У нас всего n городов, надо посетить k выбранных. Хорошо. Посещать города можно по несколько раз? Если можно, это относится и к выбранным? Можно ли заехать в выбранный город и не давать концерт? Можно ли заехать в выбранный город, после того, как дали в нем концерт? Поясните эти вопросы, пожалуйста.

@_Linkor_ · 18.11.2020, 19:45 **[ТС]**

Города, в которых надо дать концерт, нужно посетить в том порядке, в котором они вбиты
1) Можно посещать города по несколько раз. Это относится и к выбранным
2) Допустим, мы посетили А[j - 1] город и нам нужно теперь посетить город A[j], если мы туда попадаем, то концерт нужно будет провести
3) Можно заехать в выбранный город, после того как дали в нем концерт

@LegionK · 18.11.2020, 20:10

Мне кажется стоит у всех ребер поменять знак. Чтобы отрицательные стали положительными и наоборот. Потом попробовать найти отрицательный цикл, например алгоритмом Беллмана-Форда. Это значит, что можно набирать вес бесконечно. (Кроме одного случая, когда мы до этого цикла не успеем дойти. Это возможно, если путь к этому циклу проходит только через города выбранные. Это потому что вы говорите, что :

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

если мы туда попадаем, то концерт нужно будет провести

. По этой причине мне кажется, что это неправда и концерт можно сразу не давать, иначе задача усложняется сразу лишним кодом.)

Потом запустить алгоритм Флойда-Уоршелла. После чего просто идти по массиву выбранных городов и прибавлять в сумму полученное алгоритмом расстояние между a[i] и a[i+1].

В конце стоит поменять знак у суммы и вывести всё. Ну, в вашем случае ещё ответ восстановить. (Соболезную).

Код двух алгоритмов сверху лучше просто скопировать с emaxx, чтобы не ошибиться.

@_Linkor_ · 18.11.2020, 20:23 **[ТС]**

Я, возможно, вас неправильно понял, но зачем использовать алгоритм Форда-Беллмана, если алгоритмом Флойда тоже можно найти цикл? На диагонали матрицы смежности стоят не нули - признак цикла, если использовать алгоритм Флойда. Я проверял, все случаи с циклом моя программа обрабатывает корректно (писал программу, которая выводит только сообщение о цикле, и сверял тесты)

@LegionK · 18.11.2020, 21:11

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

писал программу, которая выводит только сообщение о цикле, и сверял тесты)

Ну... Не очень разбираюсь в алгоритмах с графами, поверю вам на слово.

Посмотрел ваш код, вроде все логично выглядит. Если проблема не в кратных ребрах или петлях, то и не знаю.

Может кто другой что-нибудь увидит. Но здесь я вам не смогу помочь, извините.

Могу предложить только забить на задачу и решать другую)

@LegionK 392 / 262 / 193 Регистрация: 02.05.2017 Сообщений: 1,003
	17.11.2020, 23:37	2
	Не ясно в каком порядке можно посещать города, в каком нельзя... У нас всего n городов, надо посетить k выбранных. Хорошо. Посещать города можно по несколько раз? Если можно, это относится и к выбранным? Можно ли заехать в выбранный город и не давать концерт? Можно ли заехать в выбранный город, после того, как дали в нем концерт? Поясните эти вопросы, пожалуйста. 0

@_Linkor_ 1 / 1 / 0 Регистрация: 14.06.2020 Сообщений: 7
	18.11.2020, 19:45 [ТС]	3
	Города, в которых надо дать концерт, нужно посетить в том порядке, в котором они вбиты 1) Можно посещать города по несколько раз. Это относится и к выбранным 2) Допустим, мы посетили А[j - 1] город и нам нужно теперь посетить город A[j], если мы туда попадаем, то концерт нужно будет провести 3) Можно заехать в выбранный город, после того как дали в нем концерт 0

@LegionK 392 / 262 / 193 Регистрация: 02.05.2017 Сообщений: 1,003
	18.11.2020, 20:10	4
	Мне кажется стоит у всех ребер поменять знак. Чтобы отрицательные стали положительными и наоборот. Потом попробовать найти отрицательный цикл, например алгоритмом Беллмана-Форда. Это значит, что можно набирать вес бесконечно. (Кроме одного случая, когда мы до этого цикла не успеем дойти. Это возможно, если путь к этому циклу проходит только через города выбранные. Это потому что вы говорите, что : Сообщение от _Linkor_ если мы туда попадаем, то концерт нужно будет провести . По этой причине мне кажется, что это неправда и концерт можно сразу не давать, иначе задача усложняется сразу лишним кодом.) Потом запустить алгоритм Флойда-Уоршелла. После чего просто идти по массиву выбранных городов и прибавлять в сумму полученное алгоритмом расстояние между a[i] и a[i+1]. В конце стоит поменять знак у суммы и вывести всё. Ну, в вашем случае ещё ответ восстановить. (Соболезную). Код двух алгоритмов сверху лучше просто скопировать с emaxx, чтобы не ошибиться. 0

@_Linkor_ 1 / 1 / 0 Регистрация: 14.06.2020 Сообщений: 7
	18.11.2020, 20:23 [ТС]	5
	Я, возможно, вас неправильно понял, но зачем использовать алгоритм Форда-Беллмана, если алгоритмом Флойда тоже можно найти цикл? На диагонали матрицы смежности стоят не нули - признак цикла, если использовать алгоритм Флойда. Я проверял, все случаи с циклом моя программа обрабатывает корректно (писал программу, которая выводит только сообщение о цикле, и сверял тесты) 0

@LegionK 392 / 262 / 193 Регистрация: 02.05.2017 Сообщений: 1,003
	18.11.2020, 21:11	6
	Сообщение от _Linkor_ писал программу, которая выводит только сообщение о цикле, и сверял тесты) Ну... Не очень разбираюсь в алгоритмах с графами, поверю вам на слово. Посмотрел ваш код, вроде все логично выглядит. Если проблема не в кратных ребрах или петлях, то и не знаю. Может кто другой что-нибудь увидит. Но здесь я вам не смогу помочь, извините. Могу предложить только забить на задачу и решать другую) 1