UVA 10034: MST Prim/Kruskal
Добрый вечер, я только что решил эту проблему, по крайней мере, с помощью инструмента udebug и получая во всех случаях правильный ответ. Итак, у меня более 1000 пройденных тестов, и все же, если я отправляю свой код самому судье, я получаю ошибку во время выполнения. Может кто-нибудь знать, откуда это может прийти? Мой полный здесь: код.
Алгоритм Прима:
public double primSum() {
for (Node u : nodeSet) {
u.key = Double.MAX_VALUE;
}
nodeSet.get(0).key = 0;
PriorityQueue<Node> Q = new PriorityQueue<Node>();
Q.addAll(nodeSet);
while(!Q.isEmpty()) {
Node u = Q.remove();
ArrayList<Node> adjNodes = new ArrayList<Node>();
adjNodes = getAdjNodes(u);
for (Node v : adjNodes) {
if (Q.contains(v) && adjMatrix[nodeSet.indexOf(u)][nodeSet.indexOf(v)] < v.key) {
Q.remove(v);
v.p = u;
v.key = adjMatrix[nodeSet.indexOf(u)][nodeSet.indexOf(v)];
Q.add(v);
}
}
}
double s = 0;
for (Node node : nodeSet) {
s+=node.key;
}
return s;
}