1 Отредактировано Jumbo (2011-05-12 21:24:26)

Тема: Нахождение минимального остова по алгоритму Прима

Написал прогу, вычисляющую длину минимального остовного дерева по алгоритму Прима, успешно сдал на школе программиста (http://acmp.ru/index.asp?main=task&id_task=142). Но там ограничение по вершинам 100, по рёбрам 6000, по весу 30000 и не нужно проверять граф на связность. Мне же нужно сдать задачу с вершинами до 300, рёбрами до 50000, весом до 10000 и проверкой на связность. Вроде всё нормально, но выдаёт неправильный ответ на 2 тесте, не пойму почему!

const maxN=300;
var f,f1                    :text;
    d,from                  :array[1..maxN] of int64;
    mark                    :array[1..maxN] of boolean;
    a                       :array[1..maxN,1..maxN] of int64;
    n,m,s,k,min,r           :int64;
    i,u,v                   :integer;
 
 
begin
 reset(f,'spantree.in');
 rewrite(f1,'spantree.out');
 read(f,n,m);
 for i:=1 to n do
  for v:=1 to n do a[i,v]:=-1;{заполнение матрицы смежности}
 
 for i:=1 to m do begin
   read(f,u,v,s);
   a[u,v]:=s;
   a[v,u]:=s;
 end;{считана матрица}
 close(f);
 
 for i:=2 to n do d[i]:=high(int64);
 
 while k<n do begin
 
  min:=high(int64);
  for i:=1 to n do
   if (d[i]<=min) and (not mark[i]) then begin min:=d[i]; v:=i end;
   {нахождение минимального ребра из не U в U}
   if d[v]=high(int64) then begin write(f1,'-1'); close(f1); halt end;
   if v<>1 then r:=r+a[from[v],v];{добавление ребра в ответ и в множество U}
   mark[v]:=true;{помечаем v} inc(k);
   for i:=1 to n do
    if (not mark[i]) and (a[v,i]>-1) and (a[v,i]<d[i]) then begin
     d[i]:=a[v,i];
     from[i]:=v
    end;{пробегаем соседей v и изменяем кратчайший путь до них из U}
 
 end;
  write(f1,r);
  close(f1);
end.

      

2

Re: Нахождение минимального остова по алгоритму Прима

Я конечно не гуру паскаля, т.к. не писал на нем уже очень давно, но разве максимальный integer не 32768? Если так, то количество ребер и ответ на задачу не должны в него влазить.

3 Отредактировано Jumbo (2011-05-10 23:14:18)

Re: Нахождение минимального остова по алгоритму Прима

Попробовал с int64 - тоже самое.

4

Re: Нахождение минимального остова по алгоритму Прима

v же осталось Integer.
Longint попробовать?

5

Re: Нахождение минимального остова по алгоритму Прима

V - это же номер вершины, он влезает.
Это дельфи, integer и longint одно и тоже

6

Re: Нахождение минимального остова по алгоритму Прима

В алгоритме Прима в начале выбирается наименьшее ребро и добавляется в дерево. В написанном коде вообще не понятно что добавляется в самом начале. Вроде бы это ребро из вершины 1 в никуда.

7 Отредактировано Jumbo (2011-05-11 21:39:20)

Re: Нахождение минимального остова по алгоритму Прима

Там в начале ищется минимум (он будет в вершине 1, там расстояние равно нулю) и если найдена не первая вершина, то кратчайшее расстояние добавляется в ответ.
На первом проходе не добавляется ребро "из никуда в v", там написан if.
d[ i] - текущее минимальное расстояние от первого ребра до i- ного.
Вроде так

8

Re: Нахождение минимального остова по алгоритму Прима

Алгоритм Прима предполагает что первое добавленное ребро будет минимальным в графе. Вершина 1 не обязательно инцидентна этому ребру, следовательно, она не обязательно должна быть добавлена первой в мин. остов.

9 Отредактировано Jumbo (2011-05-11 23:42:51)

Re: Нахождение минимального остова по алгоритму Прима

Искомый минимальный остов строится постепенно, добавлением в него рёбер по одному. Изначально остов полагается состоящим из единственной вершины (её можно выбрать произвольно). Затем выбирается ребро минимального веса, исходящее из этой вершины, и добавляется в минимальный остов.

С описания алгоритма Прима.
Я выбираю произвольно первую вершину, потом пробегаю её соседей, изменяю расстояние до них и на следующем проходе по циклу ищется минимальное среди путей из не добавленных вершин в множество добавленных, затем помечаю вершину куда идёт минимальное ребро (как бы добавляю ребро) и т.д.

10

Re: Нахождение минимального остова по алгоритму Прима

Хм... Да, действительно. Не зря я пишу только алгоритм Крускала smile

Ну в коде есть баги вроде: не инициализируются переменные min и v. На первой итерации они нули, а что с ними будет дальше - не известно. Минимум же не всегда будет уменьшаться, поэтому на какой-то итерации оно просто оставит вершину v с предыдущего шага.

11

Re: Нахождение минимального остова по алгоритму Прима

Минимум инициализируется min:=high(int64) в начале каждого прохода, а в процессу пробега вершин он по любому найдёт вершину равную high(int64).

12

Re: Нахождение минимального остова по алгоритму Прима

Судя по всему, вас это не очень волнует, раз за 3 дня баг не был найден. Все-таки условие нужно читать внимательно и не делать никаких предположений о том, чего в условии нет. Если в условии не сказано что в графе нет мультиребер, значит они там могут быть.

13 Отредактировано Jumbo (2011-05-12 20:07:58)

Re: Нахождение минимального остова по алгоритму Прима

Я просто её уже сдал другим алгоритмом, а с этим уже голову сломал..
А кто такие мультирёбра?

14

Re: Нахождение минимального остова по алгоритму Прима

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

15

Re: Нахождение минимального остова по алгоритму Прима

Добавил проверку - ничего не изменилось(

16

Re: Нахождение минимального остова по алгоритму Прима

Не знаю, что там не изменилось, но я взял ваш код, добавил в него проверку и оно получило Accepted.

for i:=1 to m do begin
   read(f,u,v,s);
   if (a[u][v]=-1) or (a[u][v]>s) then begin
   a[u,v]:=s;
   a[v,u]:=s;
   end;
 end;{считана матрица}

17

Re: Нахождение минимального остова по алгоритму Прима

Где вы сдавали?

18

Re: Нахождение минимального остова по алгоритму Прима

По ссылке, которая указана в первом посте. Я так понимаю, это не та версия задачи, но в таком случае нужно указывать ссылку и на вторую версию.

Кстати, если уже сдали задачу каким-то другим методом, то баг в этом ищется просто: пишется рандомный генератор и сравниваются ответы двух методов на рандомных тестах до тех пор, пока программы не выдадут различный ответ.

19

Re: Нахождение минимального остова по алгоритму Прима

Там же я написал что сдал её по этой ссылке (первоначальный вариант).
А другую версию не могу дать ссылку, туда вход для тех, кто ходит в кружок

20

Re: Нахождение минимального остова по алгоритму Прима

спасибо, Макс!