#include <cstddef>
#include <limits>
#include <algorithm>
#include <array>
#include <vector>
#include <iostream>
constexpr std::size_t GRAPH_SIZE { 7 };
using Graph = std::vector<std::vector<std::size_t>>;
using ValuesTable = std::array<std::ptrdiff_t, GRAPH_SIZE>;
bool makeStep(Graph &graph, ValuesTable &table) {
ValuesTable stepLocalTable { table };
bool result { true };
for (std::size_t i { 0 }; i < GRAPH_SIZE; i++) {
if (stepLocalTable[i] < 0) {
result = false;
continue;
}
for (const auto &adj : graph[i])
table[adj] += stepLocalTable[i];
}
return result;
}
int main() {
Graph graph {
{ 1, 2, 6 }, { 0, 3 }, { 0, 4 }, { 1, 5 }, { 2, 6, 5 }, { 3, 4 }
};
ValuesTable table {
1, -3, -5, -50, -30, -10, -250
};
std::size_t k { 0 };
for (; !makeStep(graph, table); k++)
std::cout << k;
}#include <bitset>
#include <cstddef>
#include <functional>
#include <iostream>
#include <stack>
#include <vector>
constexpr std::size_t GRAPH_SIZE { 4 };
using Graph = std::vector<std::vector<std::size_t>>;
using ValuesTable = std::array<std::ptrdiff_t, GRAPH_SIZE>;
using Visited = std::bitset<GRAPH_SIZE>;
using WithAdj = std::function<void(std::size_t, std::size_t)>;
namespace impl {
void dfs(Graph &graph, Visited &visited, WithAdj fn, std::size_t s) {
if (!visited.test(s))
visited.set(s);
for (const auto &i : graph[s]) {
fn(s, i);
if (!visited.test(i))
visited.set(i);
}
}
}
void dfs(Graph &graph, Visited &visited, WithAdj fn) {
for (std::size_t i { 0 }; i < GRAPH_SIZE; i++)
impl::dfs(graph, visited, fn, i);
}
int main() {
Visited visited;
Graph graph {
{ 1, 2 }, { 0, 2 }, { 1, 0, 3 }, { 2 }
};
ValuesTable table {
3, 2, -7, -13
};
ValuesTable iterLocalTable { table };
auto fn = [&table, &iterLocalTable](std::size_t self, std::size_t adj) {
if (iterLocalTable[self] > 0)
table[adj] += iterLocalTable[self];
};
dfs(graph, visited, fn);
for (const auto &i : table)
std::cout << i << " ";
}#include <algorithm>
#include <cstddef>
#include <array>
#include <vector>
#include <iostream>
constexpr std::size_t GRAPH_SIZE { 4 };
using Graph = std::vector<std::vector<std::size_t>>;
using ValuesTable = std::array<std::ptrdiff_t, GRAPH_SIZE>;
int main() {
Graph graph {
{ 1, 2 }, { 0, 2 }, { 0, 1, 3 }, { 2 }
};
ValuesTable table {
3, 2, -7, -13
};
ValuesTable iterLocalTable { table };
for (std::size_t i { 0 }; i < GRAPH_SIZE; i++)
for (const auto &adj : graph[i]) {
if (iterLocalTable[i] > 0)
table[adj] += iterLocalTable[i];
}
for (const auto &i : table)
std::cout << i << " ";
}