Ce problème aborde l'optimisation des profits dans le commerce de puces quantiques à travers un réseau de bases de recherche, en utilisant les algorithmes de Tarjan pour la détection des composantes fortement connexes (CFC) et le tri topologique sur le graphe condensé.
Description du Problème
Le pays D dispose de n bases de recherche et m canaux de transport. Chaque canal relie deux de ces bases. Il n'y a pas plus d'un canal direct entre deux bases. Certains canaux sont unidirectionnels, d'autres bidirectionnels (un canal bidirectionnel compte pour un seul). Le prix des "puces quantiques" varie d'une base à l'autre, mais le prix d'achat est toujours égal au prix de vente au sein d'une même base.
Un chercheur, M. Lin, voyage de la base 1 à la base n. Durant son voyage, il peut visiter la même base plusieurs fois et n'est pas tenu de visiter toutes les bases. Pour couvrir ses frais, il peut effectuer au maximum une seule transaction : acheter une puce quantique dans une base et la revendre ultérieurement dans une autre base pour réaliser un profit. S'il n'y a aucune opportunité de profit, aucune transaction n'est effectuée.
Format d'Entrée
n m
prix[1] prix[2] ... prix[n]
x1 y1 z1
x2 y2 z2
...
xm ym zm
- Première ligne : Deux entiers \(n, m\), représentant le nombre de bases et le nombre de canaux.
- Deuxième ligne : \(n\) entiers positifs, les prix des puces quantiques pour chaque base (dans l'ordre des numéros de base).
- Les m lignes suivantes : Chaque ligne contient trois entiers \(x, y, z\).
- Si \(z = 1\), un canal unidirectionnel de \(x\) vers \(y\).
- Si \(z = 2\), un canal bidirectionnel entre \(x\) et \(y\).
Contraintes des Données
- \(1 \le n \le 100000\)
- \(1 \le m \le 500000\)
- \(1 \le x, y \le n\)
- \(1 \le z \le 2\)
- Prix des puces quantiques \(\le 100\)
Format de Sortie
profit_maximal
Un entier unique, le profit maximal réalisable. Si aucun profit n'est possible, afficher 0.
Exemple
Entrée
5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2
Sortie
5
Explication de l'exemple
Structure du graphe original (les nombres entre parenthèses sont les prix des puces) :
1(4) → 2(3) ⇄ 3(5) → 5(1)
↓ ↙
4(6) ⇄⇄⇄⇄⇄⇄
Stratégies de transaction possibles :
- Chemin 1 → 2 → 3 → 5 :
- Achat à la base 2, prix 3.
- Vente à la base 3, prix 5.
- Profit = 5 - 3 = 2.
- Chemin 1 → 4 → 5 → 4 → 5 :
- Achat à la base 5, prix 1.
- Retour à la base 4 et vente, prix 6.
- Profit = 6 - 1 = 5.
Le profit optimal est donc 5.
Stratégie de Résolution
Considérons d'abord le cas d'un graphe orienté acyclique (DAG). Dans un tel graphe, le prix d'achat minimum pour atteindre un nœud peut être propagé à ses successeurs. Ainsi, pour chaque nœud, nous pouvons déterminer le prix d'achat minimal possible en amont et calculer le profit potentiel en vendant au prix actuel du nœud.
Le défi de ce problème réside dans la présence de cycles. Si deux bases se trouvent dans la même composante fortement connexe (CFC), il est possible de voyager entre elles indéfiniment. Cela signifie que le prix d'achat minimal au sein d'une CFC est simplement le minimum de tous les prix des bases qui la composent. Pour transformer le problème en une instance de DAG, nous pouvons contracter chaque CFC en un seul "super-nœud". Le problème est alors résolu sur ce graphe condensé.
De plus, il est crucial de ne considérer que les bases qui sont à la fois accessibles depuis la base de départ (base 1) et à partir desquelles la base d'arrivée (base n) est accessible. Les bases qui ne satifsont pas cette condition sont sans pertinence pour l'itinéraire et doivent être ignorées.
// Déclarations des structures de données
std::vector<int> adj_graph[MAX_NODES]; // Graphe principal
std::vector<int> rev_adj_graph[MAX_NODES]; // Graphe inversé
std::vector<int> scc_member_nodes[MAX_NODES]; // Liste des nœuds par CFC
std::vector<int> condensed_dag_edges[MAX_NODES]; // Graphe condensé (DAG des CFC)
bool visited_from_start[MAX_NODES]; // Accessible depuis le nœud 1
bool can_reach_end[MAX_NODES]; // Peut atteindre le nœud n
bool relevant_node[MAX_NODES]; // Nœud pertinent
int base_prices[MAX_NODES]; // Prix des puces
int N_bases, M_channels, tarjan_timer = 0;
int discovery_timestamps[MAX_NODES], lowest_reach_time[MAX_NODES];
std::stack<int> tarjan_stack;
bool is_on_tarjan_stack[MAX_NODES];
int node_scc_id[MAX_NODES]; // ID de la CFC à laquelle appartient le nœud
int total_sccs = 0;
int scc_min_buy_price[MAX_NODES]; // Prix minimum dans chaque CFC
int condensed_in_degree[MAX_NODES]; // Degré entrant dans le DAG condensé
const long long INF_PRICE = 2e9 + 7; // Valeur "infinie" pour les prix
std::queue<int> topological_queue;
</int></int></int></int></int></int>
Étape 1 : Filtrer les Nœuds Non Pertinents
Nous utilisons deux parcours en profondeur (DFS) pour identifier les bases qui peuvent faire partie d'un chemin valide de 1 à n.
// DFS pour vérifier l'accessibilité depuis la base de départ (1)
void dfs_forward_reach(int current_base) {
visited_from_start[current_base] = true;
for (int neighbor : adj_graph[current_base]) {
if (!visited_from_start[neighbor]) {
dfs_forward_reach(neighbor);
}
}
}
// DFS sur le graphe inversé pour vérifier si la base d'arrivée (n) est accessible depuis ce nœud
void dfs_backward_reach(int current_base) {
can_reach_end[current_base] = true;
for (int neighbor : rev_adj_graph[current_base]) {
if (!can_reach_end[neighbor]) {
dfs_backward_reach(neighbor);
}
}
}
// Appel des DFS dans la fonction principale
// dfs_forward_reach(1);
// dfs_backward_reach(N_bases);
// Marquer les nœuds valides pour le chemin
// for (int i = 1; i <= N_bases; ++i) {
// if (visited_from_start[i] && can_reach_end[i]) {
// relevant_node[i] = true;
// }
// }
Étape 2 : Détection et Condensation des Composantes Fortement Connexes (Tarjan)
L'algorithme de Tarjan est utilisé pour trouver toutes les CFC. Chaque CFC sera ensuite représentée par un super-nœud dans un nouveau graphe.
// Implémentation de l'algorithme de Tarjan pour trouver les Composantes Fortement Connexes
void tarjan_find_sccs(int u) {
discovery_timestamps[u] = lowest_reach_time[u] = ++tarjan_timer;
tarjan_stack.push(u);
is_on_tarjan_stack[u] = true;
for (int v : adj_graph[u]) {
if (!discovery_timestamps[v]) { // Voisin non visité
tarjan_find_sccs(v);
lowest_reach_time[u] = std::min(lowest_reach_time[u], lowest_reach_time[v]);
} else if (is_on_tarjan_stack[v]) { // Voisin sur la pile (arête de retour/croisée vers un ancêtre)
lowest_reach_time[u] = std::min(discovery_timestamps[v], lowest_reach_time[u]);
}
}
// Si u est la racine d'une CFC
if (discovery_timestamps[u] == lowest_reach_time[u]) {
total_sccs++;
int popped_node;
do {
popped_node = tarjan_stack.top();
tarjan_stack.pop();
is_on_tarjan_stack[popped_node] = false;
node_scc_id[popped_node] = total_sccs;
scc_member_nodes[total_sccs].push_back(popped_node);
} while (popped_node != u);
}
}
// Exécuter Tarjan pour tous les nœuds non visités (dans la fonction principale)
// for (int i = 1; i <= N_bases; ++i) {
// if (!discovery_timestamps[i] && relevant_node[i]) {
// tarjan_find_sccs(i);
// }
// }
Étape 3 : Construction du Graphe Condensé et Tri Topologique
Après avoir identifié les CFC, nous construisons un nouveau graphe où chaque nœud représente une CFC. Ce graphe condensé est un DAG. Nous calculons ensuite le prix d'achat minimum pour chaque CFC en utilisant un tri topologique.
// Initialiser le prix minimum pour chaque CFC et le degré entrant
// for (int i = 1; i <= total_sccs; ++i) {
// scc_min_buy_price[i] = INF_PRICE;
// for (int node_in_scc : scc_member_nodes[i]) {
// scc_min_buy_price[i] = std::min(scc_min_buy_price[i], base_prices[node_in_scc]);
// }
// }
// Construire le DAG des CFC et calculer les degrés entrants
// for (int u = 1; u <= N_bases; ++u) {
// if (!relevant_node[u]) continue;
// for (int v : adj_graph[u]) {
// if (!relevant_node[v]) continue;
// int scc_u = node_scc_id[u];
// int scc_v = node_scc_id[v];
// if (scc_u != scc_v) {
// condensed_dag_edges[scc_u].push_back(scc_v);
// condensed_in_degree[scc_v]++;
// }
// }
// }
// Initialiser la queue pour le tri topologique avec les CFC de degré entrant 0
// for (int i = 1; i <= total_sccs; ++i) {
// if (condensed_in_degree[i] == 0) {
// topological_queue.push(i);
// }
// }
// Effectuer le tri topologique et propager les prix minimaux
// while (!topological_queue.empty()) {
// int current_scc_id = topological_queue.front();
// topological_queue.pop();
// for (int neighbor_scc_id : condensed_dag_edges[current_scc_id]) {
// scc_min_buy_price[neighbor_scc_id] = std::min(scc_min_buy_price[neighbor_scc_id], scc_min_buy_price[current_scc_id]);
// condensed_in_degree[neighbor_scc_id]--;
// if (condensed_in_degree[neighbor_scc_id] == 0) {
// topological_queue.push(neighbor_scc_id);
// }
// }
// }
Étape 4 : Calcul du Profit Maximal
Après le tri topologique, scc_min_buy_price[i] contient le prix d'achat minimal pour une puce pouvant être revendue dans la CFC i. Nous parcourons toutes les bases valides et calculons le profit maximal possible.
// int maximum_achievable_profit = 0;
// for (int i = 1; i <= N_bases; ++i) {
// if (!relevant_node[i]) continue;
// maximum_achievable_profit = std::max(maximum_achievable_profit, (long long)base_prices[i] - scc_min_buy_price[node_scc_id[i]]);
// }
// std::cout << maximum_achievable_profit << std::endl;
Implémentation Complète
#include <iostream>
#include <vector>
#include <algorithm> // Pour std::min et std::max
#include <stack> // Pour Tarjan
#include <queue> // Pour le tri topologique
// Définitions des constantes
const int MAX_NODES = 100005;
const long long INF_PRICE = 2e9 + 7; // Utiliser long long pour éviter le débordement potentiel avec des prix
// Structures de données globales
std::vector<int> adj_graph[MAX_NODES]; // Graphe des bases
std::vector<int> rev_adj_graph[MAX_NODES]; // Graphe inversé pour reachability_to_end
std::vector<int> scc_member_nodes[MAX_NODES]; // Nœuds appartenant à chaque CFC
std::vector<int> condensed_dag_edges[MAX_NODES]; // Graphe condensé des CFC
long long scc_min_buy_price[MAX_NODES]; // Prix d'achat minimum dans chaque CFC ou provenant d'une CFC précédente
bool visited_from_start[MAX_NODES]; // Marque si un nœud est atteignable depuis la base 1
bool can_reach_end[MAX_NODES]; // Marque si la base n est atteignable depuis ce nœud
bool relevant_node[MAX_NODES]; // Vrai si le nœud est atteignable depuis 1 ET peut atteindre n
int base_prices[MAX_NODES]; // Prix des puces quantiques par base
int N_bases, M_channels;
int discovery_timestamps[MAX_NODES], lowest_reach_time[MAX_NODES];
int tarjan_timer = 0; // Compteur temporel pour Tarjan
std::stack<int> tarjan_stack; // Pile de Tarjan
bool is_on_tarjan_stack[MAX_NODES]; // Indique si un nœud est sur la pile de Tarjan
int node_scc_id[MAX_NODES]; // ID de la CFC de chaque nœud
int total_sccs = 0; // Nombre total de CFC
int condensed_in_degree[MAX_NODES]; // Degré entrant des CFC dans le graphe condensé
// Parcourt en profondeur pour déterminer l'accessibilité depuis la base de départ (1)
void dfs_forward_reach(int current_base) {
visited_from_start[current_base] = true;
for (int neighbor : adj_graph[current_base]) {
if (!visited_from_start[neighbor]) {
dfs_forward_reach(neighbor);
}
}
}
// Parcourt en profondeur sur le graphe inversé pour déterminer si la base n est atteignable depuis ce nœud
void dfs_backward_reach(int current_base) {
can_reach_end[current_base] = true;
for (int neighbor : rev_adj_graph[current_base]) {
if (!can_reach_end[neighbor]) {
dfs_backward_reach(neighbor);
}
}
}
// Implémentation de l'algorithme de Tarjan pour trouver les Composantes Fortement Connexes
void tarjan_find_sccs(int u) {
discovery_timestamps[u] = lowest_reach_time[u] = ++tarjan_timer;
tarjan_stack.push(u);
is_on_tarjan_stack[u] = true;
for (int v : adj_graph[u]) {
if (!discovery_timestamps[v]) { // Voisin non visité
tarjan_find_sccs(v);
lowest_reach_time[u] = std::min(lowest_reach_time[u], lowest_reach_time[v]);
} else if (is_on_tarjan_stack[v]) { // Voisin sur la pile (arête de retour/croisée vers un ancêtre)
lowest_reach_time[u] = std::min(discovery_timestamps[v], lowest_reach_time[u]);
}
}
// Si u est la racine d'une CFC
if (discovery_timestamps[u] == lowest_reach_time[u]) {
total_sccs++;
int popped_node;
do {
popped_node = tarjan_stack.top();
tarjan_stack.pop();
is_on_tarjan_stack[popped_node] = false;
node_scc_id[popped_node] = total_sccs;
scc_member_nodes[total_sccs].push_back(popped_node);
} while (popped_node != u);
}
}
void solve_problem() {
std::cin >> N_bases >> M_channels;
for (int i = 1; i <= N_bases; ++i) {
std::cin >> base_prices[i];
}
for (int i = 0; i < M_channels; ++i) {
int u, v, type;
std::cin >> u >> v >> type;
adj_graph[u].push_back(v);
rev_adj_graph[v].push_back(u);
if (type == 2) { // Bidirectionnel
adj_graph[v].push_back(u);
rev_adj_graph[u].push_back(v);
}
}
// Étape 1 : Filtrer les nœuds non pertinents
dfs_forward_reach(1);
dfs_backward_reach(N_bases);
for (int i = 1; i <= N_bases; ++i) {
if (visited_from_start[i] && can_reach_end[i]) {
relevant_node[i] = true;
}
}
// Étape 2 : Détection et condensation des CFC
for (int i = 1; i <= N_bases; ++i) {
if (!discovery_timestamps[i] && relevant_node[i]) { // Seulement pour les nœuds pertinents non visités
tarjan_find_sccs(i);
}
}
// Étape 3 : Construction du DAG condensé et tri topologique pour propager les prix minimaux
for (int i = 1; i <= total_sccs; ++i) {
scc_min_buy_price[i] = INF_PRICE; // Initialisation avec une valeur "infinie"
for (int node_in_scc : scc_member_nodes[i]) {
scc_min_buy_price[i] = std::min(scc_min_buy_price[i], (long long)base_prices[node_in_scc]);
}
}
for (int u = 1; u <= N_bases; ++u) {
if (!relevant_node[u]) continue;
for (int v : adj_graph[u]) {
if (!relevant_node[v]) continue;
int scc_u = node_scc_id[u];
int scc_v = node_scc_id[v];
if (scc_u != scc_v) {
condensed_dag_edges[scc_u].push_back(scc_v);
condensed_in_degree[scc_v]++;
}
}
}
for (int i = 1; i <= total_sccs; ++i) {
if (condensed_in_degree[i] == 0) {
topological_queue.push(i);
}
}
while (!topological_queue.empty()) {
int current_scc_id = topological_queue.front();
topological_queue.pop();
for (int neighbor_scc_id : condensed_dag_edges[current_scc_id]) {
// Propager le prix minimum d'achat
scc_min_buy_price[neighbor_scc_id] = std::min(scc_min_buy_price[neighbor_scc_id], scc_min_buy_price[current_scc_id]);
condensed_in_degree[neighbor_scc_id]--;
if (condensed_in_degree[neighbor_scc_id] == 0) {
topological_queue.push(neighbor_scc_id);
}
}
}
// Étape 4 : Calcul du profit maximal
long long maximum_achievable_profit = 0;
for (int i = 1; i <= N_bases; ++i) {
if (!relevant_node[i]) continue;
// Le profit est le prix de vente actuel moins le prix d'achat minimal possible jusqu'à la CFC de ce nœud
maximum_achievable_profit = std::max(maximum_achievable_profit, (long long)base_prices[i] - scc_min_buy_price[node_scc_id[i]]);
}
std::cout << maximum_achievable_profit << std::endl;
}
int main() {
std::ios_base::sync_with_stdio(false); // Optimisation I/O
std::cin.tie(nullptr); // Optimisation I/O
std::cout.tie(nullptr); // Optimisation I/O
solve_problem();
return 0;
}
</int></int></int></int></int></queue></stack></algorithm></vector></iostream>