С Новым годом! Форум программистов, компьютерный форум, киберфорум
Visual Basic
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.57/14: Рейтинг темы: голосов - 14, средняя оценка - 4.57
 Аватар для AlexKuchanskiy
1 / 1 / 1
Регистрация: 13.02.2013
Сообщений: 36

Задача на максимальный поток в Visual Basic

05.07.2013, 19:13. Показов 3041. Ответов 23
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
У меня есть граф, в нём 25 точек.

Кликните здесь для просмотра всего текста


необходимо решить задачу на максимальный поток. выходим из Донецка, приходим в Киев.
вот как я находил это на графе меньшего размера:

Кликните здесь для просмотра всего текста


а вот сам алгоритм нахождения (Форда — Фалкерсона):

1) Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью.
2) В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся.
3) Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток:
1. На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью Cmin .
2. Для каждого ребра на найденном пути увеличиваем поток на Cmin , а в противоположном ему — уменьшаем на Cmin .
3. Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.
4) Возвращаемся на шаг 2.


я сделал только часть, обнулил все потоки, но не пойму как выбрать путь из источника в сток, и что делать после этого.
вот код:
Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
Private Sub Form_Load()
Dim a()
Dim b()
Dim n As Integer
Dim Min As Integer
n = 25
ReDim a(n, n)
ReDim b(n, n)
Dim l(1 To 25) As Integer
Dim m(1 To 25) As Integer
Dim i%, j%
Dim s As String, st As String
Dim phi As String
 
For i = 1 To n ' îáíóëåíèå âñåõ çíà÷åíèé ìàññèâà ñ ðàññòîÿíèÿìè
For j = 1 To n
   a(i, j) = 0
Next j
Next i
 
a(1, 2) = 248: a(1, 5) = 337: a(1, 6) = 273
a(2, 3) = 151: a(2, 4) = 210: a(2, 5) = 133: a(2, 6) = 141
a(3, 4) = 70: a(3, 5) = 166
a(4, 5) = 156: a(4, 8) = 194: a(4, 10) = 192
a(5, 6) = 150: a(5, 7) = 172: a(5, 8) = 107
a(6, 7) = 139
a(7, 8) = 184
a(8, 9) = 118: a(8, 10) = 183
a(9, 10) = 127: a(9, 12) = 424: a(9, 14) = 341: a(9, 15) = 310: a(9, 16) = 428
a(10, 12) = 131
a(11, 12) = 492: a(11, 13) = 143: a(11, 14) = 186: a(11, 15) = 302: a(11, 18) = 337: a(11, 19) = 344: a(11, 20) = 449
a(12, 16) = 137
a(13, 14) = 297: a(13, 18) = 335: a(13, 19) = 405: a(13, 20) = 558
a(14, 15) = 137: a(14, 18) = 361: a(14, 20) = 289
a(15, 16) = 181: a(15, 19) = 245: a(15, 20) = 243: a(15, 21) = 301
a(16, 17) = 63: a(16, 20) = 319
a(17, 20) = 325: a(17, 21) = 282: a(17, 22) = 268
a(18, 19) = 170: a(18, 23) = 187
a(19, 20) = 186: a(19, 23) = 149: a(19, 24) = 391
a(20, 21) = 79: a(20, 23) = 226: a(20, 24) = 245
a(21, 22) = 388: a(21, 24) = 229
a(22, 24) = 560
a(23, 24) = 301: a(23, 25) = 341
a(24, 25) = 151
 
 
For i = 1 To n 'çàïîëíåíèå ñèììåòðè÷íîé ÷àñòè ìàññèâà ñ ðàñññòîÿíèÿìè
For j = 1 To n
   If a(i, j) <> 0 Then a(j, i) = a(i, j)
Next j
Next i
 
s = "  "
 
For i = 1 To n ' âûâîä íà÷àëüíîãî ìàññèâà ñ ðàññòîÿíèÿìè
For j = 1 To n
   s = s & a(i, j) & "   "
Next j
   s = s & vbCrLf
Next i
 
Label1.Caption = s
 
'îáíóëåíèå âñåõ ôè
For i = 1 To n
For j = 1 To n
   b(i, j) = 0
Next j
Next i
 
 
 
' âûâîä ôè
For i = 1 To n
For j = 1 To n
   phi = phi & b(i, j) & "   "
Next j
   phi = phi & vbCrLf
   
Next i
 Label2.Caption = phi
 
 
 
 
 
End Sub
Если у кого-то есть какие-то идеи, need your help
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
05.07.2013, 19:13
Ответы с готовыми решениями:

Задача по Visual Basic
Друзья , прошу у вас помощи в решении сам заочник морской академии , только пришел с рейса , денег хватило заплатить только за контракт ,...

Задача (Visual Basic)
Добрый день. Как сделать так, чтобы, когда я купил товар мне предложили бы купить что-нибудь еще. Заранее спасибо. Запрещено...

задача по информатике. Visual Basic
1.) Дано натуральни числа n і m , целые числа a1,a2...,an. Одержаты суму тих чисел даної послидовности що є ...

23
 Аватар для morgann55
1365 / 207 / 37
Регистрация: 09.02.2012
Сообщений: 745
05.07.2013, 21:09
А что у тебя в массиве a() ?? Это растояние (длина рёбер) между вершинами ?? Типа:
Visual Basic
1
a(1, 5) = 337
- означает: от вершины №1 до вершины №5 ДлинаРебра=337 Так ??
0
 Аватар для AlexKuchanskiy
1 / 1 / 1
Регистрация: 13.02.2013
Сообщений: 36
05.07.2013, 21:58  [ТС]
да, именно так
я города обозначил цифрами
0
 Аватар для morgann55
1365 / 207 / 37
Регистрация: 09.02.2012
Сообщений: 745
05.07.2013, 22:16
А сами вершины (города) имеют какие-то характеристики ?? (типа координат)
Как ты узнаешь приближаешься к цели или удаляешься ??

Добавлено через 7 минут
Или тебе не важна длина пути, а лишь бы по загруженности (цифра в красном кружке) был лучший результат ??
0
 Аватар для AlexKuchanskiy
1 / 1 / 1
Регистрация: 13.02.2013
Сообщений: 36
05.07.2013, 22:18  [ТС]
нет, имеются только расстояния от города к городу.
вот в том и дело, что мне нужно найти путь из города в город, с минимально затраченным расстоянием.

вообще по загруженности, но я принял за загруженность длину пути. потом переделаю как надо. суть всё равно не изменится
0
 Аватар для morgann55
1365 / 207 / 37
Регистрация: 09.02.2012
Сообщений: 745
05.07.2013, 22:20
Вот твой заголовок: "Задача на максимальный поток " !! Красные цифры в кружках - это что ?? (типа траффик ??)
ушёл в магаз...
0
 Аватар для AlexKuchanskiy
1 / 1 / 1
Регистрация: 13.02.2013
Сообщений: 36
05.07.2013, 22:32  [ТС]
красные цифры - пропускная способность. нужно рассчитывать по ней, но я в матрицу 25*25 уже забил не те значения, сейчас не хочу всё переделывать, долго слишком. сделаю так, а потом перепишу цифры. тут же не в них дело.
0
 Аватар для morgann55
1365 / 207 / 37
Регистрация: 09.02.2012
Сообщений: 745
05.07.2013, 23:05
Цитата Сообщение от AlexKuchanskiy Посмотреть сообщение
красные цифры - пропускная способность. нужно рассчитывать по ней, но я в матрицу 25*25 уже забил не те значения, сейчас не хочу всё переделывать, долго слишком. сделаю так, а потом перепишу цифры. тут же не в них дело.
1) Меняешь цель - меняй условие (и алгоритмы наверно)
2) Если надо ОБЯЗАТЕЛЬНО делать по твоему конспекту, то хоть обеспечь возможность ЕГО прочитать !!!! Разве там можно чего-то понять ??!! Забей в ТХТ и прикрепи....
0
 Аватар для AlexKuchanskiy
1 / 1 / 1
Регистрация: 13.02.2013
Сообщений: 36
06.07.2013, 21:46  [ТС]
сделаю, и выложу утром)

Добавлено через 19 часов 27 минут
узнал, делать не обязательно по конспекту. конспект это так, один из вариантов.
а цифры можно оставить те же, только считать их пропускной способностью.
0
 Аватар для morgann55
1365 / 207 / 37
Регистрация: 09.02.2012
Сообщений: 745
06.07.2013, 22:12
Цитата Сообщение от AlexKuchanskiy Посмотреть сообщение
а цифры можно оставить те же, только считать их пропускной способностью.
Про какие цифры ты говоришь ?? У каждого ребра ДВА параметра (две цифры)... По логике надо найти 2-3 лучших по Длине маршрута и выбрать из них (через ИХ траффик) самый оптимальный (ведь один может быть на 10-30 км длиннее, но в 2 раза свободнее). Это у тебя УчебноеЗадание или ПрикладнаяПрограмма ??
0
 Аватар для morgann55
1365 / 207 / 37
Регистрация: 09.02.2012
Сообщений: 745
07.07.2013, 03:39
Вот: забил в прогу твой Граф - покликай по соседним городам, проверь данные...
(и где твой "читаемый" конспект ?? (мне ведь тоже надо учиться ))
Вложения
Тип файла: rar Логистика.rar (562.4 Кб, 12 просмотров)
0
 Аватар для morgann55
1365 / 207 / 37
Регистрация: 09.02.2012
Сообщений: 745
07.07.2013, 09:24
Не качайте - забыл файл с Данными "зашить" !!
0
 Аватар для morgann55
1365 / 207 / 37
Регистрация: 09.02.2012
Сообщений: 745
07.07.2013, 09:36
Лучший ответ Сообщение было отмечено The trick как решение

Решение

Вот - кинул в общую папку...
Вложения
Тип файла: rar МахПоток.rar (563.0 Кб, 19 просмотров)
1
 Аватар для AlexKuchanskiy
1 / 1 / 1
Регистрация: 13.02.2013
Сообщений: 36
07.07.2013, 13:22  [ТС]
просто представить, что цифр в кружочке нет. типа у каждого ребра только одна характеристика - длина. Это учебное задание
сейчас конспект будет

Добавлено через 8 минут
а можно исходную форму посмотреть?
0
 Аватар для morgann55
1365 / 207 / 37
Регистрация: 09.02.2012
Сообщений: 745
07.07.2013, 13:30
Цитата Сообщение от AlexKuchanskiy Посмотреть сообщение
а можно исходную форму посмотреть?
Да ОНА такая же как и после компиляции
Ты бы показал как решал маленький граф (раз там получилось)...
0
 Аватар для AlexKuchanskiy
1 / 1 / 1
Регистрация: 13.02.2013
Сообщений: 36
07.07.2013, 14:43  [ТС]
вот ссылка на конспект.
надо теперь разобраться с Вашим творением. Есть исходники или код?
0
 Аватар для morgann55
1365 / 207 / 37
Регистрация: 09.02.2012
Сообщений: 745
09.07.2013, 11:28
Вот, проверяй. Правда, по Ф-Ф так и не разобрался - пришлось по своему изгаляться, но самый пропускной маршрут находит... Я так и не понял что с чем в конце складывать надо - у одних так, у других иначе ((( И примеры все типа С, С+ (с кучей слешей в коде), хоть бы кто на VB показал И у нас-то все молчат "как рыба об лёд" ??!! Ведь кто-то должен знать... Ладно, подойдёт, так составим код; нет - извиняй тогда (я вообще сначала подумал что задача по логистике )
Вложения
Тип файла: rar МахПоток.rar (569.3 Кб, 18 просмотров)
0
 Аватар для morgann55
1365 / 207 / 37
Регистрация: 09.02.2012
Сообщений: 745
09.07.2013, 20:02
Не то скомпилил опять Совсем рассеялся

Добавлено через 15 минут
Блин, файл ещё не принимает - перенемить надо... Нет, всё равно не принимается ???!!! У меня там путь при загрузке изменён - надо Rebra.txt на C: выкинуть из папки....
0
 Аватар для AlexKuchanskiy
1 / 1 / 1
Регистрация: 13.02.2013
Сообщений: 36
11.07.2013, 14:37  [ТС]
Программу закончили, вместе с morgann55, всё работает)) Но код выложу после сдачи работы преподу.
0
11.07.2013, 16:36

Не по теме:

Цитата Сообщение от AlexKuchanskiy Посмотреть сообщение
код выложу после сдачи работы преподу
Хорошо бы, а то примеров на графы -кот наплакал

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
11.07.2013, 16:36
Помогаю со студенческими работами здесь

Задача с массивами (Visual Basic)
Всем привет! Есть массив A - с кличками собак. Есть массив B - с очками, полученными каждой из собак на конкурсе. Есть массивы...

Задача c циклом в Visual Basic
Помогите пожалуйста Найти все двузначные числа, сумма цифр которых не меняется при умножении числа на 2,3,4,5,6,7,8,9 ...

Задача с массивами в Visual Basic 6.0
Даны целые числа а1, а2, а3. Получить целочисленную матрицу i,j=1,2,3, для которой bij=ai-3aj. Задача вроде и не сложная,...

Где бесплатно скачать учебник по Visual Basic 6 и Visual Basic .Net ?
Где бесплатно скачать учебник по Visual Basic 6 и Visual Basic .Net

Вычисление значений функции двух переменных в Visual Basic - Visual Basic
Помогите пожалуйста! В среде VB написать программу вычисления значений функции двух переменных. Ориентировочный вид окна программы и...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Модель микоризы: классовый агентный подход
anaschu 02.01.2026
Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .
Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути
Programma_Boinc 01.01.2026
Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Сочетание глобально распределённой вычислительной мощности и инновационных. . .
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / **********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf Пост отсюда. . .
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru