Вычислить максимальную сумму доходов от создания новой сети тоннелей метро

@alexv_red · Регистрация: 25.01.2016

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

Олимпиадное программирование.

Дается метро с N остановками и M туннелями. Две остановки называются соседними если между ними существует тоннель. Каждой остановке i присваивается доход p[i].

Нужно вычислить максимальную сумму доходов которые можно получить путем создания новой сети тоннелей, так чтобы все туннели были новыми.

Вход:
Файл metro.in содержит на строке числа N и M. На второй строке N целых чисел, каждое число содержит доход p[i] который получает остановка i. Следующие M строк содержат по два целых числа которые показывают что между этими остановками существует тоннель.

Выход:
Файл metro.out содержит одно число, максимальный доход который можно получить если построить новую сеть тоннелей.

Пример:
Объяснение: У нас N = 8 остановок и M = 10 туннелей в метро.
Сеть остановок 2-4-8 обеспечивает максимальный доход 3+5+1=9
Можно заметить что эта сеть подходит по правилам, т.к. не существует ни одного тоннеля который объединял бы остановки 2-4, 2-8 или 4-8.

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

metrou.in	metrou.out
8 10 1 3 2 5 4 1 2 1 1 2 2 3 3 4 4 5 5 3 3 6 2 6 2 7 7 8 8 3	9

@a1d4r · 10.04.2016, 13:29

Немного не понял условие. Почему, например, нельзя взять маршрут 2-4-6-8?
По теории графов могу посоветовать informatics.mccme.ru/course/view.php?id=6

@alexv_red · 10.04.2016, 13:58 **[ТС]**

потому что в маршруте 2-4-6-8 есть построенный тоннель 2-6

@a1d4r · 10.04.2016, 14:05

Для 2-4-6-8 нужно построить тоннели 2-4, 4-6, 6-8 и 2-8. Не увидел тут тоннеля 2-6. Или нужно, чтобы тоннели были между всеми остановками сети?

@alexv_red · 10.04.2016, 18:56 **[ТС]**

скажу честно, понятие не имею, но видно так оно и есть

Добавлено через 2 часа 21 минуту
Нужно создать такую сеть чтобы:
1. ЛЮБЫЕ две взятые остановки не были соседними
2. Сумма доходов должна быть максимальной

@a1d4r · 10.04.2016, 20:35

Попробуй создать матрицу смежности графа, в котором любые две вершины соединены (a[1..MaxN, 1..MaxN]). Удали ребра, которые совпадают с входными данными (a[i, j] = -1). Дальше перебирай вершины, чтобы для каждых двух вершин i и j a[i, j] <> -1. Найди такие вершины, для которых стоимость максимальна. Перебирать нужно не "в лоб", а подобрать нужный алгоритм, например с помощью ДП, либо жадным алгоритмом, в зависимости от ограничений на входные данные.

@alexv_red · 11.04.2016, 07:22 **[ТС]**

Не совсем понял. Можешь написать код.
Заранее спасибо!

Добавлено через 1 час 20 минут
вот что получилось, выдает ошибку - переполнение стека, также не разрешает создать матрицу [1..100000, 1..100000]

Pascal

Program P1;
type metrou = array[1..10000] of integer;
     nat = -1..0;
var f: text;
    N: 1..100000;
    M: 1..150000;
    p, h: metrou;
    StInt: array[1..100, 1..100] of nat;
    i, max, a, b: integer;
Procedure Prelucrare(x, k, m: integer; h: metrou);
var i: integer;
begin
    for i:= x+1 to N do
        if StInt[i,x]= -1 then h[i]:= -1;
    m := m + p[x];
    if (k > 1) and (m > max) then 
        max := m;   
    k := k + 1;
    for i:= x+1 to N do
        if h[i] <> -1 then Prelucrare(i, k, m, h);
end;
begin
    Assign(f, 'metro.in');
    Reset(f);
    Readln(f, N, M);
    Writeln(M);
    for i := 1 to N do
        Read(f, p[i]);
    Readln(f);
    for i := 1 to M do begin
        Readln(f, a, b);
        StInt[a, b] := -1;
        StInt[b, a] := -1;
    end;
    Readln;
    Close(f);
    max := 0;
    for i := 1 to N do 
        Prelucrare(i, 1, 0, h);
    Writeln('max=',max);
    Readln;
end.

Prelucrare(x, k, m: integer; h: metrou);
x- номер остановки которую добавляем в сеть
к - номер остановок в сети(нельзя создать сеть из одной остановки)
m - доход от предыдущих остановок
h - список разрешаемых остановок (которые можно добавить в сеть, если h[i]=-1 значит остановку i нельзя добавить)

Добавлено через 9 часов 3 минуты

Pascal

Program P1;
type
    nat = -1..0;
    metrou = array[1..1000] of nat;
    lim = 1..10000;
var f: text;
    N: 1..100000;
    M: 1..150000;
    h: metrou;
    p: array[1..1000] of lim;
    StInt: array[1..100, 1..100] of nat;
    i, max, a, b: integer;
Procedure Prelucrare(x, k, m: integer; h: metrou);
var i, l: integer;
y:string;
begin
  if x <= N then begin
    for i:= x+1 to N do
        if StInt[x,i]= -1 then h[i]:= -1;
    m := m + p[x];
    if (k > 1) and (m > max) then
        max := m;
    for i:= x+1 to N do
        if h[i] <> -1 then
            Prelucrare(i, k+1, m, h);
  end;
end;
begin
    Assign(f, 'metro.in');
    Reset(f);
    Readln(f, N, M);
    for i := 1 to N do
        Read(f, p[i]);
    Readln(f);
    for i := 1 to M do begin
        Readln(f, a, b);
        StInt[a, b] := -1;
        StInt[b, a] := -1;
    end;
    Close(f);
    max := 0;
    for i := 1 to N do
        Prelucrare(i, 1, 0, h);
    Writeln('max=',max);
    Readln;
end.

Вроде работает, но все равно нельзя расширить матрицу скажем на 1000*1000

@a1d4r 44 / 44 / 66 Регистрация: 22.07.2015 Сообщений: 191
	10.04.2016, 13:29	2
	Немного не понял условие. Почему, например, нельзя взять маршрут 2-4-6-8? По теории графов могу посоветовать informatics.mccme.ru/course/view.php?id=6 0

@alexv_red 2 / 2 / 0 Регистрация: 25.01.2016 Сообщений: 31
	10.04.2016, 13:58 [ТС]	3
	потому что в маршруте 2-4-6-8 есть построенный тоннель 2-6 0

@a1d4r 44 / 44 / 66 Регистрация: 22.07.2015 Сообщений: 191
	10.04.2016, 14:05	4
	Для 2-4-6-8 нужно построить тоннели 2-4, 4-6, 6-8 и 2-8. Не увидел тут тоннеля 2-6. Или нужно, чтобы тоннели были между всеми остановками сети? 0

@alexv_red 2 / 2 / 0 Регистрация: 25.01.2016 Сообщений: 31
	10.04.2016, 18:56 [ТС]	5
	скажу честно, понятие не имею, но видно так оно и есть Добавлено через 2 часа 21 минуту Нужно создать такую сеть чтобы: 1. ЛЮБЫЕ две взятые остановки не были соседними 2. Сумма доходов должна быть максимальной 0

@a1d4r 44 / 44 / 66 Регистрация: 22.07.2015 Сообщений: 191
	10.04.2016, 20:35	6
	Попробуй создать матрицу смежности графа, в котором любые две вершины соединены (a[1..MaxN, 1..MaxN]). Удали ребра, которые совпадают с входными данными (a[i, j] = -1). Дальше перебирай вершины, чтобы для каждых двух вершин i и j a[i, j] <> -1. Найди такие вершины, для которых стоимость максимальна. Перебирать нужно не "в лоб", а подобрать нужный алгоритм, например с помощью ДП, либо жадным алгоритмом, в зависимости от ограничений на входные данные. 0

	11.04.2016, 07:22