Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
167 / 167 / 30
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
1

Правильность алгоритма Диница

02.04.2014, 11:20. Показов 1430. Ответов 0
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Вот код моего алгоритма Диница.Но вот незадача - на всех моих ручных тестах он работает, а как отправить тестить куда-нибудь - так на многих тестах WA получает. Может кто подскажет, в чём тут может быть беда, а?
C++
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
88
89
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
 
using namespace std;
typedef long long ll;
 
const ll maxv = 10000, maxe = 100000;
ll ef[maxe], es[maxe], ev[maxe], first[maxv], nexti[maxe], c = 0, n, m, s, t, inf = 9999999999LL;
vector<char> good(maxe, true);
vector<ll> level(maxv, 0);
queue<ll> q;
 
void add(ll v1, ll v2, ll val)
{
    nexti[++c] = first[v1]; first[v1] = c;
    ef[c] = v1; es[c] = v2; ev[c] = val;
}
 
void input()
{
    cin >> n >> m >> s >> t;
    ll x, y, z;
    for (ll i = 0; i<m; ++i)
    {
        cin >> x >> y >> z;
        add(x, y, z);
    }
}
 
void bfs()
{
    q.push(s);
    level[s] = 1;
    while (!q.empty())
    {
        ll v = q.front(); q.pop();
        for (ll h = first[v]; h; h = nexti[h])
        if (ev[h] > 0 && level[es[h]] == 0)
        {
            level[es[h]] = level[v] + 1;
            q.push(es[h]);
        }
    }
}
 
ll dfs(ll v, ll flow)
{
    if (v == t) return flow;
    ll temp = 0, res = 0;
    for (ll h = first[v]; h; h = nexti[h])
    {
        if (ev[h]>0 && level[es[h]] == level[v] + 1)
        {
            temp = dfs(es[h], min(flow, ev[h]));
            if (temp == 0)
            {
                ev[h] = 0;
                return 0;
            }
            ev[h] -= temp;
            res += temp;
        }
    }
    return res;
}
 
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    input();
    ll flow = 0, ans = 0;
    do
    {
        bfs();
        ans = dfs(s, inf);
        flow += ans;
        level.clear();
        level.resize(n+1);
    } while (ans);
    cout << flow;
    system("pause");
    return 0;
}
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
02.04.2014, 11:20
Ответы с готовыми решениями:

Проверьте, пожалуйста, правильность составленного мной алгоритма)
Вот код: #include &lt;iostream&gt; #include &lt;stdlib.h&gt; #include &lt;stdio.h&gt; int main() { FILE...

Реализация алгоритма Диница над графами в виде матриц смежности
Попытка перевода кода из C++ в C#. Большая просьба исправить ошибки. А главное - что и как здесь...

Проверьте правильность составленного алгоритма. Делфи
Здравствуйте, проверьте, пожалуйста, правильно ли я составил данный алгоритм. Надеюсь поможете,...

проверьте пожалуйста правильность блок схемы алгоритма
program Project2; {$APPTYPE CONSOLE} uses SysUtils; const n=100; var a: array of integer;...

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

Правильность решения задания и алгоритма, проверяющего, попарную различность 4 чисел
Есть задание(из книги Макконнела &quot;Основы современных алгоритмов&quot;): Напишите алгоритм, проверяющий,...

Алгоритм Диница
Доброго времени суток! Тут возникла проблема с пониманием вышеназванного алгоритма. Точнее, с одной...

Графы, алгоритм Диница (реализовать граф списком смежности)
У меня есть готовая программа по алгоритму Диница, но граф в матричном представлении. Очень нужно...

Нахождение максимального потока в простейшем графе по алгоритму Диница
Есть такой вот неориентированный граф с пропускными способностями рёбер равными единице....


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Новые блоги и статьи
Элементы алгоритмизации
hw_wired 28.01.2025
Основы алгоритмизации В современном мире алгоритмы играют фундаментальную роль в развитии информационных технологий и программирования. Понимание основ алгоритмизации является ключевым элементом в. . .
Человек и информация
hw_wired 28.01.2025
Введение: роль информации в познании мира В современном мире информация играет фундаментальную роль в процессе познания окружающей действительности. Она представляет собой совокупность сведений об. . .
Компьютер и информация
hw_wired 28.01.2025
Эволюция вычислительных машин История развития вычислительной техники начинается задолго до появления первых электронных устройств. Человечество всегда стремилось упростить процесс вычислений и. . .
Информационные технологии
hw_wired 28.01.2025
Введение в современные технологии работы с информацией В современном мире информационные технологии стали неотъемлемой частью практически всех сфер человеческой деятельности. Они существенно. . .
Информация вокруг нас
hw_wired 28.01.2025
Основные понятия информации В современном мире понятие информации является фундаментальным и охватывает практически все сферы человеческой деятельности. Информация представляет собой совокупность. . .
Компьютер для начинающих
hw_wired 28.01.2025
Введение в мир компьютерных технологий В современном мире информация стала одним из важнейших ресурсов человечества, определяющим развитие общества и технологий. Наша жизнь неразрывно связана с. . .
[golang] 189. Rotate Array
alhaos 28.01.2025
Повороты рукоятки, целочисленный слайс нужно сдвинуть на целое положительное число. Мне очень нравится решение на GO / / https:/ / leetcode. com/ studyplan/ top-interview-150/ package topInterview . . .
КуМир: решение задач на матрицы
bytestream 28.01.2025
КуМир представляет собой среду для обучения программированию, которая включает в себя мощные инструменты для работы с матрицами. Матрица в программировании - это двумерный массив, состоящий из. . .
КуМир: решение задач на строки
bytestream 28.01.2025
В системе программирования КуМир работа со строковыми данными является одним из важнейших аспектов создания программ. Строки представляют собой последовательности символов, заключенные в кавычки,. . .
КуМир: решение геометрических задач
bytestream 28.01.2025
Программирование геометрических задач в среде КуМир становится всё более актуальным в обучении школьников и студентов. КуМир — это разработанная в России обучающая программная среда, предназначенная. . .
КуМир, исполнитель Водолей: Задачи и решения
bytestream 28.01.2025
КуМир — это образовательная среда для обучения программированию. Она предлагает пользователям разнообразные инструменты для разработки и отладки программ, что особенно ценно для студентов и. . .
КуМир, исполнитель Чертежник: Решение задач
bytestream 28.01.2025
КуМир (Комплект Учебных МИРов) представляет собой образовательную среду для обучения основам программирования и алгоритмизации. Исполнитель Чертежник работает на координатной плоскости, где может. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru