Тема: Алгоритм прима
В условии:
if (g[v][to] < min_e[to])разве не следует добавить
if (g[v][to] < min_e[to] && !used[to])?
Re: Алгоритм прима
на результат это не повлияет..
А вот с выводом похоже надо
if (min_e[v] != -1)
cout << v << " " << min_e[v] << endl;
поменять на
if (sel_e[v] != -1)
cout << v << " " << sel_e[v] << endl;
Re: Алгоритм прима
И в сличае с n^2... 
5 2011-10-30 07:36:56 Отредактировано Astekinane (2011-10-30 07:41:05)
Re: Алгоритм прима
И всё-таки я думаю, что алгоритм где-то некорректен, например для примера:
6 9
4 5 10
4 3 5
5 3 3
5 0 8
0 3 5
0 1 3
0 2 2
1 2 6
2 3 7
Алгоритм выдаёт:
2 0
1 0
5 0
5 3
3 5
Хотя ребро (5,3) и ребро (3,5) - это одно и то же. Копировал точно с исходников.
(Кстати, поздравляю с седьмым местом в контесте на этой неделе на CF).