Flux Maximum
L'algorithme de Dinic est une méthode efficace pour résoudre le problème du flux maximum dans un réseau. Il opère en construisant un graphe de niveaux et en trouvant des chemins augmentants bloquants.
Implémentation Dinic pour le Flux Maximum
Problème de référence : P3376 【Modèle】Flux Maximum de Réseau
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
// Utilisation de long long pour les capacités afin de gérer de grandes valeurs
using CapacityType = long long;
const CapacityType INF = 1e18; // Une valeur suffisamment grande pour l'infini
struct Edge {
int to;
CapacityType capacity;
int reverse_edge_idx; // Index de l'arête inverse dans la liste d'adjacence
};
std::vector<std::vector<Edge>> adj;
std::vector<int> level; // Niveaux des nœuds pour le graphe de niveaux
std::vector<int> current_edge_ptr; // Pointeur pour l'arête actuelle dans DFS (optimisation)
int num_nodes, num_edges, source_node, sink_node;
// Ajoute une arête orientée et son arête inverse (résiduelle)
void add_directed_edge(int u, int v, CapacityType cap) {
adj[u].push_back({v, cap, static_cast<int>(adj[v].size())});
adj[v].push_back({u, 0, static_cast<int>(adj[u].size()) - 1}); // Arête résiduelle avec capacité 0
}
// Construit le graphe de niveaux en utilisant BFS
bool build_level_graph() {
std::fill(level.begin(), level.end(), -1);
std::queue<int> q;
level[source_node] = 0;
q.push(source_node);
while (!q.empty()) {
int u = q.front();
q.pop();
for (const auto& edge : adj[u]) {
if (edge.capacity > 0 && level[edge.to] == -1) {
level[edge.to] = level[u] + 1;
q.push(edge.to);
}
}
}
return level[sink_node] != -1; // Retourne vrai si le puits est atteignable
}
// Trouve un chemin augmentant dans le graphe de niveaux en utilisant DFS
CapacityType find_augmenting_path(int u, CapacityType flow_limit) {
if (u == sink_node) {
return flow_limit;
}
CapacityType pushed_flow = 0;
// Parcourir les arêtes à partir du pointeur actuel (optimisation)
for (int& i = current_edge_ptr[u]; i < adj[u].size(); ++i) {
Edge& edge = adj[u][i];
if (level[edge.to] == level[u] + 1 && edge.capacity > 0) {
CapacityType path_flow = find_augmenting_path(edge.to, std::min(flow_limit - pushed_flow, edge.capacity));
if (path_flow == 0) {
continue; // Impossible d'envoyer du flow par ce chemin
}
edge.capacity -= path_flow;
adj[edge.to][edge.reverse_edge_idx].capacity += path_flow;
pushed_flow += path_flow;
if (pushed_flow == flow_limit) {
break; // Limite de flow atteinte
}
}
}
return pushed_flow;
}
// Algorithme de Dinic
CapacityType dinic_max_flow() {
CapacityType total_max_flow = 0;
while (build_level_graph()) {
std::fill(current_edge_ptr.begin(), current_edge_ptr.end(), 0); // Réinitialiser les pointeurs d'arêtes
while (CapacityType path_flow = find_augmenting_path(source_node, INF)) {
total_max_flow += path_flow;
}
}
return total_max_flow;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cin >> num_nodes >> num_edges >> source_node >> sink_node;
adj.resize(num_nodes + 1);
level.resize(num_nodes + 1);
current_edge_ptr.resize(num_nodes + 1);
for (int i = 0; i < num_edges; ++i) {
int u, v;
CapacityType w;
std::cin >> u >> v >> w;
add_directed_edge(u, v, w);
}
std::cout <>> dinic_max_flow() << std::endl;
return 0;
}
Flux à Coût Minimum Maximal
Le problème du flux à coût minimum maximal (Min-Cost Max-Flow) cherche à envoyer la quantité maximale de flux de la source au puits tout en minimisant le coût total de ce flux. Une approche courante est l'algorithme des chemins augmentants de coût minimum, qui utilise SPFA ou Dijkstra avec des potentiels pour trouver les chemins de coût minimum dans le graphe résiduel.
Implémentation pour le Flux à Coût Minimum Maximal
Problème de référence : P3381 【Modèle】Flux à Coût Minimum Maximal
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <utility> // For std::pair
// Utilisation de long long pour les capacités et les coûts si nécessaire
using CapacityType = int; // Selon les contraintes du problème, int peut suffire
using CostType = long long;
const CapacityType FLOW_INF = std::numeric_limits<CapacityType>::max();
const CostType COST_INF = std::numeric_limits<CostType>::max();
struct EdgeMCF {
int to;
CapacityType capacity;
CostType cost;
int reverse_edge_idx;
};
std::vector<std::vector<EdgeMCF>> adj_mcf;
std::vector<CostType> potentials; // Potentiels pour Dijkstra avec coûts réduits
std::vector<CostType> distances; // Distances de la source dans le graphe résiduel
std::vector<int> parent_edge; // Pour reconstruire le chemin
std::vector<int> parent_node; // Pour reconstruire le chemin
std::vector<bool> in_queue; // Pour SPFA
std::vector<bool> visited_dfs; // Pour DFS
int num_nodes_mcf, num_edges_mcf, source_node_mcf, sink_node_mcf;
CapacityType total_flow_mcf;
CostType total_cost_mcf;
// Ajoute une arête orientée avec capacité et coût, et son arête inverse
void add_directed_edge_mcf(int u, int v, CapacityType cap, CostType cost) {
adj_mcf[u].push_back({v, cap, cost, static_cast<int>(adj_mcf[v].size())});
adj_mcf[v].push_back({u, 0, -cost, static_cast<int>(adj_mcf[u].size()) - 1});
}
// Initialise les potentiels des nœuds avec SPFA
void initialize_potentials_spfa() {
potentials.assign(num_nodes_mcf + 1, COST_INF);
in_queue.assign(num_nodes_mcf + 1, false);
std::queue<int> q;
potentials[source_node_mcf] = 0;
q.push(source_node_mcf);
in_queue[source_node_mcf] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
in_queue[u] = false;
for (const auto& edge : adj_mcf[u]) {
if (edge.capacity > 0 && potentials[edge.to] > potentials[u] + edge.cost) {
potentials[edge.to] = potentials[u] + edge.cost;
if (!in_queue[edge.to]) {
q.push(edge.to);
in_queue[edge.to] = true;
}
}
}
}
}
// Trouve le chemin de coût minimum de la source au puits en utilisant Dijkstra avec potentiels
bool find_shortest_path_dijkstra() {
distances.assign(num_nodes_mcf + 1, COST_INF);
parent_node.assign(num_nodes_mcf + 1, -1);
parent_edge.assign(num_nodes_mcf + 1, -1);
// priority_queue pour Dijkstra: pair {distance, node_idx}
std::priority_queue<std::pair<CostType, int>, std::vector<std::pair<CostType, int>>, std::greater<std::pair<CostType, int>>> pq;
distances[source_node_mcf] = 0;
pq.push({0, source_node_mcf});
while (!pq.empty()) {
CostType d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (d > distances[u]) {
continue;
}
for (int i = 0; i < adj_mcf[u].size(); ++i) {
EdgeMCF& edge = adj_mcf[u][i];
// Coût réduit: actual_cost = original_cost + potential[u] - potential[v]
CostType reduced_cost = edge.cost + potentials[u] - potentials[edge.to];
if (edge.capacity > 0 && distances[edge.to] > distances[u] + reduced_cost) {
distances[edge.to] = distances[u] + reduced_cost;
parent_node[edge.to] = u;
parent_edge[edge.to] = i;
pq.push({distances[edge.to], edge.to});
}
}
}
return distances[sink_node_mcf] != COST_INF; // Retourne vrai si le puits est atteignable
}
// Algorithme du Flux à Coût Minimum Maximal
void min_cost_max_flow() {
total_flow_mcf = 0;
total_cost_mcf = 0;
// Initialiser les potentiels (nécessaire si le graphe contient des coûts négatifs ou est arbitraire)
initialize_potentials_spfa();
while (find_shortest_path_dijkstra()) {
// Mettre à jour les potentiels après chaque itération de Dijkstra
for (int i = 1; i <= num_nodes_mcf; ++i) {
if (distances[i] != COST_INF) { // Seulement pour les nœuds atteignables
potentials[i] += distances[i];
}
}
// Trouver le flux maximum qui peut être envoyé sur ce chemin de coût minimum
CapacityType path_flow = FLOW_INF;
for (int v = sink_node_mcf; v != source_node_mcf; v = parent_node[v]) {
path_flow = std::min(path_flow, adj_mcf[parent_node[v]][parent_edge[v]].capacity);
}
// Mettre à jour les capacités et le coût total
total_flow_mcf += path_flow;
for (int v = sink_node_mcf; v != source_node_mcf; v = parent_node[v]) {
EdgeMCF& edge = adj_mcf[parent_node[v]][parent_edge[v]];
edge.capacity -= path_flow;
adj_mcf[edge.to][edge.reverse_edge_idx].capacity += path_flow;
total_cost_mcf += path_flow * edge.cost; // Utiliser le coût original
}
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cin >> num_nodes_mcf >> num_edges_mcf >> source_node_mcf >> sink_node_mcf;
adj_mcf.resize(num_nodes_mcf + 1);
for (int i = 0; i < num_edges_mcf; ++i) {
int u, v;
CapacityType w;
CostType c;
std::cin >> u >> v >> w >> c;
add_directed_edge_mcf(u, v, w, c);
}
min_cost_max_flow();
std::cout << total_flow_mcf << " " << total_cost_mcf << std::endl;
return 0;
}
Flux de Réseau avec Bornes Inférieures et Supérieures
Les problèmes de flux avec bornes (Lower and Upper Bounded Flow) généralisent les problèmes de flux stendard en ajoutant des contraintes de borne inférieure sur la quantité de flux que chaque arête doit transporter, en plus de la borne supérieure (capacité). Ces problèmes peuvant être transformés en problèmes de flux maximum classiques et résolus avec Dinic.
Flux Faisable avec Bornes (sans source ni puits explicites)
Recherche d'un flux qui satisfait toutes les bornes inférieures et supérieures, et qui respecte la conservation du flux à chaque nœud.
Problème de référence : Loj 115
#include <iostream>
#include <vector>
#include <queue>
#include <numeric> // For std::iota
#include <algorithm> // For std::min, std::fill
using CapacityType = long long;
const CapacityType DINIC_INF = 1e18; // Une valeur suffisamment grande pour l'infini
struct DinicEdge {
int to;
CapacityType capacity;
int reverse_edge_idx;
};
std::vector<std::vector<DinicEdge>> dinic_adj;
std::vector<int> dinic_level;
std::vector<int> dinic_current_edge_ptr;
int dinic_num_nodes; // Nombre de nœuds dans le graphe Dinic (peut inclure super-source/puits)
void dinic_add_edge(int u, int v, CapacityType cap) {
dinic_adj[u].push_back({v, cap, static_cast<int>(dinic_adj[v].size())});
dinic_adj[v].push_back({u, 0, static_cast<int>(dinic_adj[u].size()) - 1});
}
bool dinic_bfs(int s_dinic, int t_dinic) {
std::fill(dinic_level.begin(), dinic_level.end(), -1);
std::queue<int> q;
dinic_level[s_dinic] = 0;
q.push(s_dinic);
while (!q.empty()) {
int u = q.front();
q.pop();
for (const auto& edge : dinic_adj[u]) {
if (edge.capacity > 0 && dinic_level[edge.to] == -1) {
dinic_level[edge.to] = dinic_level[u] + 1;
q.push(edge.to);
}
}
}
return dinic_level[t_dinic] != -1;
}
CapacityType dinic_dfs(int u, int t_dinic, CapacityType flow_limit) {
if (u == t_dinic) {
return flow_limit;
}
CapacityType pushed_flow = 0;
for (int& i = dinic_current_edge_ptr[u]; i < dinic_adj[u].size(); ++i) {
DinicEdge& edge = dinic_adj[u][i];
if (dinic_level[edge.to] == dinic_level[u] + 1 && edge.capacity > 0) {
CapacityType path_flow = dinic_dfs(edge.to, t_dinic, std::min(flow_limit - pushed_flow, edge.capacity));
if (path_flow == 0) continue;
edge.capacity -= path_flow;
dinic_adj[edge.to][edge.reverse_edge_idx].capacity += path_flow;
pushed_flow += path_flow;
if (pushed_flow == flow_limit) break;
}
}
return pushed_flow;
}
CapacityType calculate_dinic_flow(int s_dinic, int t_dinic) {
CapacityType total_max_flow = 0;
while (dinic_bfs(s_dinic, t_dinic)) {
std::fill(dinic_current_edge_ptr.begin(), dinic_current_edge_ptr.end(), 0);
while (CapacityType path_flow = dinic_dfs(s_dinic, t_dinic, DINIC_INF)) {
total_max_flow += path_flow;
}
}
return total_max_flow;
}
struct OriginalNetworkEdge {
int u, v;
CapacityType lower_bound, upper_bound;
int dinic_edge_idx; // Index de l'arête dans le graphe Dinic
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N_original, M_original;
std::cin >> N_original >> M_original;
std::vector<OriginalNetworkEdge> original_edges(M_original);
for (int i = 0; i < M_original; ++i) {
std::cin >> original_edges[i].u >> original_edges[i].v >> original_edges[i].lower_bound >> original_edges[i].upper_bound;
}
// Nœuds additionnels pour la super-source S_super et le super-puit T_super
int S_super = 0; // Utiliser 0 pour la super-source
int T_super = N_original + 1; // Utiliser N_original + 1 pour le super-puit
dinic_num_nodes = N_original + 2; // N_original nœuds + S_super + T_super
dinic_adj.assign(dinic_num_nodes + 1, std::vector<DinicEdge>());
dinic_level.resize(dinic_num_nodes + 1);
dinic_current_edge_ptr.resize(dinic_num_nodes + 1);
std::vector<CapacityType> balance(N_original + 1, 0); // Différence entre in-flow requis et out-flow requis
for (int i = 0; i < M_original; ++i) {
int u = original_edges[i].u;
int v = original_edges[i].v;
CapacityType L = original_edges[i].lower_bound;
CapacityType U = original_edges[i].upper_bound;
// Ajouter l'arête avec capacité U - L dans le graphe Dinic
dinic_add_edge(u, v, U - L);
original_edges[i].dinic_edge_idx = static_cast<int>(dinic_adj[u].size()) - 1; // Index de l'arête directe
// Mettre à jour le bilan des flux
balance[u] -= L;
balance[v] += L;
}
CapacityType required_flow_from_s_super = 0;
for (int i = 1; i <= N_original; ++i) {
if (balance[i] > 0) { // Nœud avec un surplus de flux entrant requis
dinic_add_edge(S_super, i, balance[i]);
required_flow_from_s_super += balance[i];
} else if (balance[i] < 0) { // Nœud avec un déficit de flux entrant requis
dinic_add_edge(i, T_super, -balance[i]);
}
}
CapacityType flow_found = calculate_dinic_flow(S_super, T_super);
if (flow_found == required_flow_from_s_super) {
std::cout << "YES\n";
for (int i = 0; i < M_original; ++i) {
int u_orig = original_edges[i].u;
// Le flux sur l'arête (u_orig, v_orig) est sa borne inférieure + le flux résiduel
// L'arête résiduelle a l'index (dinic_edge_idx ^ 1) si elle est stockée
// dans la liste d'adjacence du noeud de destination (original_edges[i].v)
// Ou, plus simplement, c'est la capacité de l'arête inverse de l'arête de Dinic originale.
// La capacité restante de l'arête directe dans dinic_adj[u_orig][original_edges[i].dinic_edge_idx]
// est U - L - (flow through this edge).
// Donc, le flow through this edge = (U - L) - capacity_left.
// Et le flow total = L + (flow through this edge).
CapacityType current_flow_on_edge = original_edges[i].lower_bound +
(original_edges[i].upper_bound - original_edges[i].lower_bound -
dinic_adj[u_orig][original_edges[i].dinic_edge_idx].capacity);
std::cout << current_flow_on_edge << "\n";
}
} else {
std::cout << "NO\n";
}
return 0;
}
Flux Maximum avec Bornes (avec source et puits explicites)
Pour un réseau avec bornes et une source s et un puits t explicites, on cherche le flux maximum possible de s à t qui satisfait toutes les bornes. La transformation ajoute une arête de t à s avec une capacité infinie pour permettre au flux de circuler en cercle.
Problème de référence : Loj 116
#include <iostream>
#include <vector>
#include <queue>
#include <numeric>
#include <algorithm>
using CapacityType = long long;
const CapacityType DINIC_INF_MAX = 1e18;
struct DinicEdge {
int to;
CapacityType capacity;
int reverse_edge_idx;
};
std::vector<std::vector<DinicEdge>> dinic_adj;
std::vector<int> dinic_level;
std::vector<int> dinic_current_edge_ptr;
int dinic_num_nodes_max;
void dinic_add_edge(int u, int v, CapacityType cap) {
dinic_adj[u].push_back({v, cap, static_cast<int>(dinic_adj[v].size())});
dinic_adj[v].push_back({u, 0, static_cast<int>(dinic_adj[u].size()) - 1});
}
bool dinic_bfs(int s_dinic, int t_dinic) {
std::fill(dinic_level.begin(), dinic_level.end(), -1);
std::queue<int> q;
dinic_level[s_dinic] = 0;
q.push(s_dinic);
while (!q.empty()) {
int u = q.front();
q.pop();
for (const auto& edge : dinic_adj[u]) {
if (edge.capacity > 0 && dinic_level[edge.to] == -1) {
dinic_level[edge.to] = dinic_level[u] + 1;
q.push(edge.to);
}
}
}
return dinic_level[t_dinic] != -1;
}
CapacityType dinic_dfs(int u, int t_dinic, CapacityType flow_limit) {
if (u == t_dinic) {
return flow_limit;
}
CapacityType pushed_flow = 0;
for (int& i = dinic_current_edge_ptr[u]; i < dinic_adj[u].size(); ++i) {
DinicEdge& edge = dinic_adj[u][i];
if (dinic_level[edge.to] == dinic_level[u] + 1 && edge.capacity > 0) {
CapacityType path_flow = dinic_dfs(edge.to, t_dinic, std::min(flow_limit - pushed_flow, edge.capacity));
if (path_flow == 0) continue;
edge.capacity -= path_flow;
dinic_adj[edge.to][edge.reverse_edge_idx].capacity += path_flow;
pushed_flow += path_flow;
if (pushed_flow == flow_limit) break;
}
}
return pushed_flow;
}
CapacityType calculate_dinic_flow(int s_dinic, int t_dinic) {
CapacityType total_max_flow = 0;
while (dinic_bfs(s_dinic, t_dinic)) {
std::fill(dinic_current_edge_ptr.begin(), dinic_current_edge_ptr.end(), 0);
while (CapacityType path_flow = dinic_dfs(s_dinic, t_dinic, DINIC_INF_MAX)) {
total_max_flow += path_flow;
}
}
return total_max_flow;
}
struct OriginalNetworkEdge {
int u, v;
CapacityType lower_bound, upper_bound;
int dinic_edge_idx;
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N_original, M_original, S_original, T_original;
std::cin >> N_original >> M_original >> S_original >> T_original;
std::vector<OriginalNetworkEdge> original_edges(M_original);
for (int i = 0; i < M_original; ++i) {
std::cin >> original_edges[i].u >> original_edges[i].v >> original_edges[i].lower_bound >> original_edges[i].upper_bound;
}
int S_super_f = 0; // Super-source pour la phase de faisabilité
int T_super_f = N_original + 1; // Super-puit pour la phase de faisabilité
dinic_num_nodes_max = N_original + 2;
dinic_adj.assign(dinic_num_nodes_max + 1, std::vector<DinicEdge>());
dinic_level.resize(dinic_num_nodes_max + 1);
dinic_current_edge_ptr.resize(dinic_num_nodes_max + 1);
std::vector<CapacityType> balance(N_original + 1, 0);
for (int i = 0; i < M_original; ++i) {
int u = original_edges[i].u;
int v = original_edges[i].v;
CapacityType L = original_edges[i].lower_bound;
CapacityType U = original_edges[i].upper_bound;
dinic_add_edge(u, v, U - L);
original_edges[i].dinic_edge_idx = static_cast<int>(dinic_adj[u].size()) - 1;
balance[u] -= L;
balance[v] += L;
}
// Ajoute l'arête spéciale du puits original à la source originale avec capacité infinie
// pour permettre au flux de circuler en boucle lors de la recherche du flux max faisable.
// Cela compte pour le flux initial (flow_on_t_s_edge).
int t_s_edge_idx = static_cast<int>(dinic_adj[T_original].size());
dinic_add_edge(T_original, S_original, DINIC_INF_MAX);
CapacityType required_flow_from_s_super = 0;
for (int i = 1; i <= N_original; ++i) {
if (balance[i] > 0) {
dinic_add_edge(S_super_f, i, balance[i]);
required_flow_from_s_super += balance[i];
} else if (balance[i] < 0) {
dinic_add_edge(i, T_super_f, -balance[i]);
}
}
CapacityType feasibility_flow = calculate_dinic_flow(S_super_f, T_super_f);
if (feasibility_flow != required_flow_from_s_super) {
std::cout << "please go home to sleep\n"; // Ou "Pas de solution faisable"
return 0;
}
// Une fois la faisabilité établie, nous avons un flux valide (possiblement 0 si toutes les bornes inférieures sont 0).
// Le flux initial de t à s est la capacité restante sur l'arête t->s APRÈS la phase de faisabilité.
CapacityType initial_flow_t_s = dinic_adj[T_original][t_s_edge_idx].capacity;
// Réinitialiser les capacities des arêtes du super-graphe pour le calcul du flux max s-t
// Ne pas reset les arêtes originales et l'arête t->s
for(int u = 0; u <= N_original + 1; ++u) {
for(auto& edge : dinic_adj[u]) {
// Remettre la capacité des arêtes du super-graphe (S_super_f, T_super_f) à 0
// pour qu'elles n'interfèrent pas avec le calcul du flux max s-t
// Attention: Il faut faire cela sans perturber le graphe de flux résiduel des arêtes originales.
// Une manière plus propre serait de reconstruire le graphe sans ces arêtes, ou d'utiliser un flag.
// Pour simplifier et éviter de reconstruire, on peut set la capacité à 0 pour ces arêtes
// s'ils ne sont pas les arêtes (t_original, s_original) ou les arêtes d'origine
if ((u == S_super_f && edge.to >= 1 && edge.to <= N_original) ||
(edge.to == T_super_f && u >= 1 && u <= N_original)) {
edge.capacity = 0; // Ces arêtes ont servi à la faisabilité et ne doivent plus exister
dinic_adj[edge.to][edge.reverse_edge_idx].capacity = 0; // L'inverse aussi
}
}
}
// Calculer le flux maximum de S_original à T_original sur le graphe résiduel
CapacityType max_flow_s_t = calculate_dinic_flow(S_original, T_original);
// Le flux total de s à t est le flux max trouvé PLUS le flux déjà établi sur l'arête t->s (soustrait de son INF)
// C'est le flux qui a circulé à travers l'arête t->s dans le sens inverse.
// La capacité restante de l'arête (T_original, S_original) était 'initial_flow_t_s'.
// Le flow qui a circulé de S_original à T_original à travers l'arête (T_original, S_original) est
// initial_flow_t_s - dinic_adj[T_original][t_s_edge_idx].capacity
CapacityType final_max_flow = initial_flow_t_s - dinic_adj[T_original][t_s_edge_idx].capacity + max_flow_s_t;
std::cout << final_max_flow << std::endl;
return 0;
}
Flux Minimum avec Bornes (avec source et puits explicites)
Pour trouver le flux minimum de s à t, on utilise une transformation similaire. Après avoir assuré la faiasbilité, on remplace l'arête (t, s) par une arête (s, t) avec capacité infinie, puis on cherche le flux minimum en exécutant Dinic de t à s.
Problème de référence : Loj 117
#include <iostream>
#include <vector>
#include <queue>
#include <numeric>
#include <algorithm>
using CapacityType = long long;
const CapacityType DINIC_INF_MIN = 1e18;
struct DinicEdge {
int to;
CapacityType capacity;
int reverse_edge_idx;
};
std::vector<std::vector<DinicEdge>> dinic_adj;
std::vector<int> dinic_level;
std::vector<int> dinic_current_edge_ptr;
int dinic_num_nodes_min;
void dinic_add_edge(int u, int v, CapacityType cap) {
dinic_adj[u].push_back({v, cap, static_cast<int>(dinic_adj[v].size())});
dinic_adj[v].push_back({u, 0, static_cast<int>(dinic_adj[u].size()) - 1});
}
bool dinic_bfs(int s_dinic, int t_dinic) {
std::fill(dinic_level.begin(), dinic_level.end(), -1);
std::queue<int> q;
dinic_level[s_dinic] = 0;
q.push(s_dinic);
while (!q.empty()) {
int u = q.front();
q.pop();
for (const auto& edge : dinic_adj[u]) {
if (edge.capacity > 0 && dinic_level[edge.to] == -1) {
dinic_level[edge.to] = dinic_level[u] + 1;
q.push(edge.to);
}
}
}
return dinic_level[t_dinic] != -1;
}
CapacityType dinic_dfs(int u, int t_dinic, CapacityType flow_limit) {
if (u == t_dinic) {
return flow_limit;
}
CapacityType pushed_flow = 0;
for (int& i = dinic_current_edge_ptr[u]; i < dinic_adj[u].size(); ++i) {
DinicEdge& edge = dinic_adj[u][i];
if (dinic_level[edge.to] == dinic_level[u] + 1 && edge.capacity > 0) {
CapacityType path_flow = dinic_dfs(edge.to, t_dinic, std::min(flow_limit - pushed_flow, edge.capacity));
if (path_flow == 0) continue;
edge.capacity -= path_flow;
dinic_adj[edge.to][edge.reverse_edge_idx].capacity += path_flow;
pushed_flow += path_flow;
if (pushed_flow == flow_limit) break;
}
}
return pushed_flow;
}
CapacityType calculate_dinic_flow(int s_dinic, int t_dinic) {
CapacityType total_max_flow = 0;
while (dinic_bfs(s_dinic, t_dinic)) {
std::fill(dinic_current_edge_ptr.begin(), dinic_current_edge_ptr.end(), 0);
while (CapacityType path_flow = dinic_dfs(s_dinic, t_dinic, DINIC_INF_MIN)) {
total_max_flow += path_flow;
}
}
return total_max_flow;
}
struct OriginalNetworkEdge {
int u, v;
CapacityType lower_bound, upper_bound;
int dinic_edge_idx;
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N_original, M_original, S_original, T_original;
std::cin >> N_original >> M_original >> S_original >> T_original;
std::vector<OriginalNetworkEdge> original_edges(M_original);
for (int i = 0; i < M_original; ++i) {
std::cin >> original_edges[i].u >> original_edges[i].v >> original_edges[i].lower_bound >> original_edges[i].upper_bound;
}
int S_super_f = 0; // Super-source pour la phase de faisabilité
int T_super_f = N_original + 1; // Super-puit pour la phase de faisabilité
dinic_num_nodes_min = N_original + 2;
dinic_adj.assign(dinic_num_nodes_min + 1, std::vector<DinicEdge>());
dinic_level.resize(dinic_num_nodes_min + 1);
dinic_current_edge_ptr.resize(dinic_num_nodes_min + 1);
std::vector<CapacityType> balance(N_original + 1, 0);
for (int i = 0; i < M_original; ++i) {
int u = original_edges[i].u;
int v = original_edges[i].v;
CapacityType L = original_edges[i].lower_bound;
CapacityType U = original_edges[i].upper_bound;
dinic_add_edge(u, v, U - L);
original_edges[i].dinic_edge_idx = static_cast<int>(dinic_adj[u].size()) - 1;
balance[u] -= L;
balance[v] += L;
}
// Ajoute l'arête spéciale du puits original à la source originale avec capacité infinie
// L'arête t->s est nécessaire pour la faisabilité.
// L'index de cette arête est important pour retrouver sa capacité résiduelle.
int t_s_edge_original_idx_in_adj = static_cast<int>(dinic_adj[T_original].size());
dinic_add_edge(T_original, S_original, DINIC_INF_MIN);
CapacityType required_flow_from_s_super = 0;
for (int i = 1; i <= N_original; ++i) {
if (balance[i] > 0) {
dinic_add_edge(S_super_f, i, balance[i]);
required_flow_from_s_super += balance[i];
} else if (balance[i] < 0) {
dinic_add_edge(i, T_super_f, -balance[i]);
}
}
CapacityType feasibility_flow = calculate_dinic_flow(S_super_f, T_super_f);
if (feasibility_flow != required_flow_from_s_super) {
std::cout << "please go home to sleep\n"; // Ou "Pas de solution faisable"
return 0;
}
// Le flux initial de t à s, après la phase de faisabilité.
// C'est la capacité de l'arête résiduelle (S_original, T_original) dans le graphe Dinic
// juste avant cette arête (T_original, S_original) est parcourue.
// Plus précisément, c'est le flux qui circule de S_original à T_original via l'arête (T_original, S_original).
// Sa capacité résiduelle représente la quantité de flux qui peut encore être envoyée dans le "cercle".
CapacityType initial_flow_t_s_residual_capacity = dinic_adj[T_original][t_s_edge_original_idx_in_adj].capacity;
// Réinitialiser les capacities des arêtes du super-graphe S_super_f / T_super_f.
// Mettre à 0 les capacités des arêtes reliant S_super_f ou T_super_f aux nœuds originaux.
for(int u = 0; u <= N_original + 1; ++u) {
for(auto& edge : dinic_adj[u]) {
if ((u == S_super_f && edge.to >= 1 && edge.to <= N_original) ||
(edge.to == T_super_f && u >= 1 && u <= N_original)) {
edge.capacity = 0;
dinic_adj[edge.to][edge.reverse_edge_idx].capacity = 0;
}
}
}
// Pour trouver le flux minimum, nous maximisons le flux de T_original à S_original
// dans le graphe résiduel actuel (après la phase de faisabilité).
// La maximisation du flux de T_original vers S_original réduira le flux de S_original vers T_original.
CapacityType flow_to_remove = calculate_dinic_flow(T_original, S_original);
// Le flux minimum de S_original à T_original est le flux initial qui passait par (T_original, S_original)
// moins le flux que nous avons réussi à renvoyer de T_original à S_original.
// Le flux initial via (T_original, S_original) était DINIC_INF_MIN - initial_flow_t_s_residual_capacity.
// Ce flux a été forcé par la phase de faisabilité.
// Le flux min est (Flow initial de s à t) - (max flow de t à s dans le graphe résiduel).
// Le 'flux initial de s à t' est donné par la capacité de l'arête (t,s) dans le graphe Dinic final.
// La capacité de (T_original, S_original) est le flux qui *ne peut pas* être renvoyé.
// Donc, DINIC_INF_MIN - (capacité résiduelle de (T_original, S_original)) est le flux MINIMUM de S_original à T_original.
// Le flux qui a traversé l'arête (T_original, S_original) dans le graphe résiduel est (DINIC_INF_MIN - dinic_adj[T_original][t_s_edge_original_idx_in_adj].capacity)
// C'est le flux initial que nous avons poussé de S_original à T_original.
// Ensuite, on enlève le flux max qu'on peut envoyer de T_original à S_original.
CapacityType min_flow_s_t = (DINIC_INF_MIN - initial_flow_t_s_residual_capacity) - flow_to_remove;
std::cout << min_flow_s_t << std::endl;
return 0;
}