Problème 1 : Emplacement optimal de l'hôpital
Description du problème
Considérons un arbre binaire, comme illustré ci-dessous :
Les valeurs dans les nœuds représentent la population des résidents, et les numéros à côté sont les identifiants des nœuds. L'objectif est de construire un hôpital sur un nœud de sorte que la somme des distances parcourues par tous les résidents soit minimale, avec une distance de $1$ entre nœuds adjacents. Par exemple, si l'hôpital est placé au nœud 1, la somme des distances est $4+12+2\times20+2\times40=136$ ; s'il est au nœud 3, la somme devient $4\times2+13+20+40=81$.
Format d'entrée
La première ligne contient un entier $n$ indiquant le nombre de nœuds.
Les $n$ lignes suivantes décrivent chaque nœud avec trois entiers $w, u, v$ : $w$ est la population du nœud, $u$ est le lien vers le fils gauche (0 si absent), et $v$ est le lien vers le fils droit (0 si absent).
Format de sortie
Un entier représentant la somme minimale des distances.
Exemple #1
Entrée exemple #1
5
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0
Sortie exemple #1
81
Contraintes
Pour $100\%$ des données, $1 \leq n \leq 100$, $0 \leq u, v \leq n$, $1 \leq w \leq 10^5$.
Solution 1 : Approche par force brute avec BFS
Pour chaque nœud comme candidat hospitalier, nous calculons la somme des distances à tous les autres nœuds via BFS pour déterminer les niveaux, puis un BFS supplémentaire pour accumuler les distances pondérées. Cette méthode a une complexité temporelle d'environ $O(n^2 \log n)$, similaire à SPFA.
// Solution par force brute en C++
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int TAILLE_MAX = 550;
int nb_noeuds, population[TAILLE_MAX], matrice_adj[TAILLE_MAX][TAILLE_MAX];
int distance[TAILLE_MAX];
void calculer_distances(int depart) {
memset(distance, 0x3f, sizeof(distance));
queue<int> file;
file.push(depart);
distance[depart] = 0;
while (!file.empty()) {
int courant = file.front(); file.pop();
for (int voisin = 1; voisin <= nb_noeuds; ++voisin) {
if (matrice_adj[courant][voisin] && distance[voisin] > distance[courant] + 1) {
distance[voisin] = distance[courant] + 1;
file.push(voisin);
}
}
}
}
int somme_distance_totale(int hopital) {
calculer_distances(hopital);
int total = 0;
for (int i = 1; i <= nb_noeuds; ++i) {
if (i != hopital) total += distance[i] * population[i];
}
return total;
}
int main() {
cin >> nb_noeuds;
memset(matrice_adj, 0, sizeof(matrice_adj));
for (int i = 1; i <= nb_noeuds; ++i) {
int w, u, v;
cin >> w >> u >> v;
population[i] = w;
if (u != 0) matrice_adj[i][u] = matrice_adj[u][i] = 1;
if (v != 0) matrice_adj[i][v] = matrice_adj[v][i] = 1;
}
int min_total = 0x3f3f3f3f;
for (int i = 1; i <= nb_noeuds; ++i) {
min_total = min(min_total, somme_distance_totale(i));
}
cout << min_total << endl;
return 0;
}
Solution 2 : Utilisation du centre de l'arbre
Pour un arbre, le nœud qui minimise la somme des distances est le centre de l'arbre (le nœud où la sous-arbre la plus lourde est minimisée). Cela réduit la complexité à $O(n \log n)$.
// Solution avec le centre de l'arbre en C++
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int TAILLE_MAX = 10010;
int nb_noeuds, population[TAILLE_MAX], population_totale = 0;
int matrice_adj[TAILLE_MAX][TAILLE_MAX];
int poids_max_ss_arbre[TAILLE_MAX], somme_ss_arbre[TAILLE_MAX];
int meilleur_noeud, poids_min = 0x3f3f3f3f;
void parcours_profondeur(int noeud, int parent) {
somme_ss_arbre[noeud] = population[noeud];
poids_max_ss_arbre[noeud] = 0;
for (int voisin = 1; voisin <= nb_noeuds; ++voisin) {
if (matrice_adj[noeud][voisin] && voisin != parent) {
parcours_profondeur(voisin, noeud);
somme_ss_arbre[noeud] += somme_ss_arbre[voisin];
poids_max_ss_arbre[noeud] = max(poids_max_ss_arbre[noeud], somme_ss_arbre[voisin]);
}
}
poids_max_ss_arbre[noeud] = max(poids_max_ss_arbre[noeud], population_totale - somme_ss_arbre[noeud]);
if (poids_max_ss_arbre[noeud] < poids_min) {
poids_min = poids_max_ss_arbre[noeud];
meilleur_noeud = noeud;
}
}
void calculer_resultat() {
memset(distance, 0x3f, sizeof(distance));
queue<int> file;
file.push(meilleur_noeud);
distance[meilleur_noeud] = 0;
while (!file.empty()) {
int courant = file.front(); file.pop();
for (int voisin = 1; voisin <= nb_noeuds; ++voisin) {
if (matrice_adj[courant][voisin] && distance[voisin] > distance[courant] + 1) {
distance[voisin] = distance[courant] + 1;
file.push(voisin);
}
}
}
int resultat = 0;
for (int i = 1; i <= nb_noeuds; ++i) {
if (i != meilleur_noeud) resultat += distance[i] * population[i];
}
cout << resultat << endl;
}
int main() {
cin >> nb_noeuds;
memset(matrice_adj, 0, sizeof(matrice_adj));
for (int i = 1; i <= nb_noeuds; ++i) {
int w, u, v;
cin >> w >> u >> v;
population[i] = w;
population_totale += w;
if (u != 0) matrice_adj[i][u] = matrice_adj[u][i] = 1;
if (v != 0) matrice_adj[i][v] = matrice_adj[v][i] = 1;
}
parcours_profondeur(1, 0);
calculer_resultat();
return 0;
}
Problème 2 : Labyrinthe binaire (01)
Description du problème
On donne une grille $n \times n$ remplie de $0$ et $1$. Départ d'une cellule contenant $0$, vous pouvez vous déplacer vers une cellule adjacente (haut, bas, gauche, droite) contenant $1$, et inversement. Pour chaque requête, calculer le nombre de cellules accessibles à partir d'une cellule donnée (incluse).
Format d'entrée
La première ligne contient deux entiers positifs $n$ et $m$.
Les $n$ lignes suivantes contiennent chacune $n$ caractères (0 ou 1) sans espaces.
Les $m$ lignes suivantes contiennent deux entiers $i$ et $j$, représentant la cellule de départ pour la requête.
Format de sortie
Pour chaque requête, afficher le nombre de cellules accessibles.
Exemple #1
Entrée exemple #1
2 2
01
10
1 1
2 2
Sortie exemple #1
4
4
Contraintes
Pour $20\%$ des données, $n \leq 10$ ; pour $40\%$, $n \leq 50$ ; pour $50\%$, $m \leq 5$ ; pour $60\%$, $n,m \leq 100$ ; pour $100\%$, $1 \leq n \leq 1000$, $1 \leq m \leq 100000$.
Solution 1 : BFS pour chaque requête
Une approche naïve effectue un BFS pour chaque requête, obtenant 70 points. Elle peut être coûteuse en temps pour de grandes valeurs de $m$.
// Solution par BFS individuel en C++
#include <iostream>
#include <cstring>
#include <queue>
#include <utility>
using namespace std;
const int TAILLE_MAX = 1010;
int taille_grille, nb_requetes;
char grille[TAILLE_MAX][TAILLE_MAX];
bool visite[TAILLE_MAX][TAILLE_MAX];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int bfs(int x_depart, int y_depart) {
memset(visite, false, sizeof(visite));
queue<pair<int, int>> file;
file.push({x_depart, y_depart});
visite[x_depart][y_depart] = true;
int compteur = 1;
while (!file.empty()) {
auto [x, y] = file.front(); file.pop();
for (int dir = 0; dir < 4; ++dir) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx >= 1 && nx <= taille_grille && ny >= 1 && ny <= taille_grille && !visite[nx][ny] && grille[nx][ny] != grille[x][y]) {
visite[nx][ny] = true;
compteur++;
file.push({nx, ny});
}
}
}
return compteur;
}
int main() {
cin >> taille_grille >> nb_requetes;
for (int i = 1; i <= taille_grille; ++i) {
for (int j = 1; j <= taille_grille; ++j) {
cin >> grille[i][j];
}
}
for (int q = 0; q < nb_requetes; ++q) {
int x, y;
cin >> x >> y;
cout << bfs(x, y) << endl;
}
return 0;
}
Solution 2 : Coloration des composantes connexes
Pour optimiser, on utilise la coloration des composantes connexes. Lors du premier parcours d'une cellule, on attribue un identifiant à toutes les cellules du même composant et on stocke sa taille. Les requêtes ultérieures sur n'importe quelle cellule de ce composant retournent directement cette taille. Cela améliore la complexité à $O(n^2 + m)$.
// Solution avec coloration par DFS en C++
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int TAILLE_MAX = 1010;
int taille_grille, nb_requetes;
char grille[TAILLE_MAX][TAILLE_MAX];
int id_composant[TAILLE_MAX][TAILLE_MAX];
int taille_composant[1000010];
int prochain_id = 0;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
void parcours_profondeur(int x, int y, int id) {
id_composant[x][y] = id;
taille_composant[id]++;
for (int dir = 0; dir < 4; ++dir) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx >= 1 && nx <= taille_grille && ny >= 1 && ny <= taille_grille && id_composant[nx][ny] == -1 && grille[nx][ny] != grille[x][y]) {
parcours_profondeur(nx, ny, id);
}
}
}
int main() {
cin >> taille_grille >> nb_requetes;
memset(id_composant, -1, sizeof(id_composant));
for (int i = 1; i <= taille_grille; ++i) {
for (int j = 1; j <= taille_grille; ++j) {
cin >> grille[i][j];
}
}
for (int q = 0; q < nb_requetes; ++q) {
int x, y;
cin >> x >> y;
if (id_composant[x][y] == -1) {
parcours_profondeur(x, y, prochain_id++);
}
cout << taille_composant[id_composant[x][y]] << endl;
}
return 0;
}