|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Stanislav Shwartsman 2:400/520 29 Jun 2001 13:23:48
To : Aleksey Mashihin
Subject : help
--------------------------------------------------------------------------------
28 Jun 01 22:41, you wrote to All:
AM> Краны расположены в узлах (1,2,3,4,5,.. КРА
Ы )
AM> Если перекрыть 5 кран то в 6 и 7 уже не будет воды
AM> Если 1 закрыть то вообще нигде не будет воды .
AM> Я использовал алгаритм Дейкстры, но он как-то не правильно работает
AM> Т.е. если есть схема типа 1--2--3--4 и перекрыть 3 кран, то он все
AM> равно пишет что в 4 вода есть !
AM> Если кто знает напишите плз. по работе надо, там у меня есть карта
AM> города со схемой газопровода, и кранов будет около 1000 так что
AM> рекурсия не покатит.
Для начала строим граф по следующей схеме. Если вода подходит к какой-то
вершине и кран закрыт, убираем нафиг для дуги, изходящие из этой вершины.
Из того, что отсталось ищем компоненты связности с помощью DFS. Вода есть
только в тех вершинах, которые находятся в одном компоненте связности
с источником воды.
E-mail: gate@fidonet.org.il
Voice Phones: 972-4-8330554 (home), 972-5-4481073 (cell)
Bye !
Stanislav (AKA Night's Man) [Team Technion]
---
* Origin: Gate From Another World ... From Haifa, Israel (2:400/520)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
help |
Aleksey Mashihin |
28 Jun 2001 22:41:36 |
 Re: help |
andyc@nikom.tagil.ru |
29 Jun 2001 13:31:56 |
  help |
Stanislav Shwartsman |
29 Jun 2001 13:26:57 |
 Re: help |
andyc@nikom.tagil.ru |
02 Jul 2001 07:18:02 |
|
help |
Stanislav Shwartsman |
29 Jun 2001 13:23:48 |
|
help |
Aleksey Mashihin |
01 Jul 2001 01:37:10 |
|
help |
Stanislav Shwartsman |
02 Jul 2001 15:31:39 |
|
help |
Ivan Mak |
29 Jun 2001 23:38:05 |
|
help |
Aleksey Mashihin |
01 Jul 2001 01:41:34 |
|
help |
Ivan Mak |
01 Jul 2001 16:43:31 |
|
|
