BitNeBolt
@BitNeBolt

Почему не работает такое решение?

Задача: определить, есть ли в графе отрицательный цикл. Что предлагает emaxx. Я решил действовать немного по-другому: находить цикл в графе и проверять его вес. Вот программа:
import java.util.Scanner;

import java.util.Deque;
import java.util.ArrayDeque;

public class NegativeWeightCycle {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[][] graph = new int[n][n];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				graph[i][j] = sc.nextInt();
			}
		}

		sc.close();

		boolean[] visited = new boolean[n];
		boolean[] inStack = new boolean[n];
		//edgeTo[i] - вершина, из которой попали в i
		int[] edgeTo = new int[n];

		for (int i = 0; i < n; i++) {
			if (!visited[i]) {
				Deque<Integer> stack = new ArrayDeque<>();
				stack.offerFirst(i);

				while (!stack.isEmpty()) {
					int v = stack.getFirst();

					if (inStack[v]) {
						v = stack.pollFirst();
						inStack[v] = false;
						continue;
					}

					//аналогичный подход при обыном обнаружении цкилов, только вместо покраски
					//проверка, находится ли вершина в стеке (название пошло от рекурсивного дфс)
					//а так испольщуются увета вершин
					inStack[v] = true;
					visited[v] = true;

					for (int j = 0; j < n; j++) {
						int dist = graph[v][j];

						//100000 - значит ребра между вершинами нет
						if (dist != 100000) {
							if (inStack[j]) {
								int from = edgeTo[j]; //для восстановелния, если цикл неотр.
								edgeTo[j] = v;

								int pathWeight = graph[v][j];
								int iter = v;
								while (iter != j) {
									pathWeight += graph[edgeTo[iter]][iter];
									iter = edgeTo[iter];
								}

								if (pathWeight < 0) {
									System.out.println("YES");
									return;
								} else {
									//восстановлние
									edgeTo[j] = from;
								}

							} else if (!visited[j]) {
								//возможно, помечать, что вершина в стеке логичнее здесь, но вроде
								//не имеет разницы
								stack.offerFirst(j);
								edgeTo[j] = v;
							}
						}
					}
				}
			}
		}

		System.out.println("NO");
	}
}


На каком графе она спотыкается, если не может пройти 24-й тест?
Сама задача.
  • Вопрос задан
  • 124 просмотра
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
У вас простой DFS. Если ему не повезет пойти не по отрицательному циклу, но при этом обойти какие-то его вершины, то вы запорите перебор и этот цикл никогда не найдется.

Чтобы через DFS найти отрицательный цикл - придется перебирать ВСЕ циклы. Для этого надо не помечать вершины как visited. Правда, работать будет очень медленно и почти гарантированно не пройдет по time limit, ибо циклов в гарфе может быть экспоненциально много.

Edit, вот вам пример. В графе только один отрицательный цикл 1->2->3->1. Но есть еще ребро 1->3. Если вы начнете из 1-ой вершины, потом возьмете ребро 1->3, то дальше вы из вершины 3 никуда не сможете пойти, уберете ее из стека и пометите как visited. Далее вы рассмотрите ребро 1->2 а потом из вершины 2 ребро 2->3 вы пропустите, потому что вершина 3 уже visited.

Этот пример можно бесконечно усложнять - все зависит от того в каком порядке будут обходится ребра в каждой вершине.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы