Installation des réservoires et robinets dans un quartier - Programmation compétitive
Ces dernières années, nous remarquons qu'il n'y a pas eu assez de pluie, ce qui entraîne un faible volume d'eau dans tous les barrages du Maroc. Pour cette raison, il peut y avoir des problèmes pour desservir les maisons en eau cet été.
Ainsi, les autorités des villes qui auront ce problème, par exemple Zagora, ont décidé d'installer des réservoirs dans certaines maisons qui fourniront de l'eau potable à d'autres maisons via des tuyaux, de sorte que chaque maison ait au plus un tuyau d'arrivé et au plus un tuyau de sortie. Une question se pose alors : où devrions-nous installer les réservoirs et les robinets ? Les réservoirs sont simplement installés dans les maisons ayant un tuyau de sortie mais pas de tuyau d'arrivé, et dans les maisons n'ayant qu'un tuyau d'arrivé et pas de tuyau de sortie, il y a un robinet. Le comité chargé de fournir l'eau potable a décidé de créer un réseau efficace.
Entrée
L'entrée contiendra deux nombres n, et p désigne le nombre de maisons et de tuyaux, les autres t ligne suivantes contientront les connexions de tuyaux entre les maisons, chaque connexion contiennent trois valeurs d'entrée : f_i, t_i, d_i désignant le tuyau de diamètre d_i de la maison f_i à la maison t_i.
Sortie
La sortie contiendra le nombre de paires de réservoirs et de robinets t installés dans la première ligne et les t lignes suivantes contiendront trois nombres entiers : le numéro de maison du réservoir, le numéro de maison du robinet et le diamètre minimum du tuyau entre eux.
Exemples
Entrée du programme | Sortie du programme |
---|---|
8 5 5 8 35 2 1 30 4 3 20 1 5 20 6 7 25 | 3 2 8 20 4 3 20 6 7 25 |
9 6 7 4 98 5 9 72 4 6 10 2 8 22 9 7 17 3 1 66 | 3 2 8 22 3 1 66 5 6 10 |
Solution
A partir de l'énoncé du problème, nous pouvons faire les observations suivantes :
- Une maison avec un tuyau de sortie mais pas de tuyau d'arrivé se voit installer un réservoir.
- Une maison avec un tuyau d'arrivé mais sans tuyau de sortie reçoit un robinet.
À partir du premier exemple d'entrée, nous pouvons dessiner un graphe orienté des connexions des différents composants/maisons pour déterminer le nombre de réservoirs et de robinets à installer.
La figure ci-dessus représente les maisons connectées fournies dans l'entrée sous forme de graphe. Découvrons où placer les réservoirs et les robinets dans cette configuration.
- En 2->8, 2 n'a qu'un tuyau de sortie, il aura donc un réservoir installé. 8 n'a qu'un tuyau d'arrivée, il y aura donc un robinet installé. Puisqu'il n'y a pas d'autres maisons connectées, le diamètre minimum sera de 20.
- De même, en 4->3, 4 a un tuyau de départ donc un réservoir et 3 a un tuyau d'arrivée donc un robinet. Ici, le diamètre minimum est de 20.
- Enfin, en 6->7, 6 a un tuyau de départ donc un réservoir et 7 a un tuyau d'arrivée donc un robinet. Ici le diamètre minimum est de 25.
L'approche
Effectuez un parcours DFS ou BFS à partir des maisons appropriées pour trouver toutes les différentes composantes connectées. Le nombre de composants connectés différents est notre réponse t.
Les t lignes suivantes de la sortie sont le début de la composante connectée, la fin de la composante connectée et le diamètre minimum du début à la fin de la composante connectée dans chaque ligne.
Étant donné que les réservoirs ne peuvent être installés que sur les maisons ayant un tuyau sortant et aucun tuyau entrant, ce sont donc des maisons appropriées pour démarrer DFS (ou BFS) à partir de c'est-à-dire effectuer DFS (ou BFS) à partir de ces maisons non visitées.
#include <iostream> #include <cstring> #include <vector> #include <stack> #include <set> #include <algorithm> #include <climits> using namespace std; // Construire la matrice d'adjacence pour le graphe class GraphAdjList{ private: vector<vector<int>> voisins; vector<vector<int>> diametres; int nbMaisons; public: GraphAdjList(const vector<vector<int>> &tab, int nb_maisons){ nbMaisons=nb_maisons; int n=tab.size(); voisins.resize(nb_maisons); diametres.resize(nb_maisons); // tab[i][0] => f_i ; tab[i][1] => t_i ; tab[i][2] => d_i // pour chaque f_i, t_i, d_i for(int i=0; i < n; i++){ // ajouter t_i dans la liste d'adjacence de f_i voisins[tab[i][0]].push_back(tab[i][1]); // le diamètre entre f_i et t_i est d_i diametres[tab[i][0]].push_back(tab[i][2]); } } const vector<vector<int>> & getVoisins(){return voisins;} const vector<vector<int>> & getDiametres(){return diametres;} int getNbMaisons(){return nbMaisons;} }; vector<int> parcours_largeur(GraphAdjList reseau, int depart){ vector<int> connected; bool visited[reseau.getNbMaisons()]; memset(visited, false, sizeof(visited)); stack<int> pile; pile.push(depart); while(pile.size()>0){ int current = pile.top(); pile.pop(); if(!visited[current]){ connected.push_back(current); visited[current] = true; for(int v:reseau.getVoisins()[current]){ pile.push(v); } } } return connected; } void solution(vector<vector<int>> tuyaux, int n){ GraphAdjList reseau(tuyaux,n+1); // Stockez tous les noeuds avec des arêtes sortants qui sont des réservoirs set<int>reservoires; // Stocker tous les noeuds dont les arêtes entrants sont des robinets. set<int>robinets; for(vector<int>tuyau:tuyaux){ robinets.insert(tuyau[1]); } for(vector<int>tuyau:tuyaux){ if(robinets.count(tuyau[0]) <= 0){ // Ajouter des maisons avec uniquement des tuyaux entrants aux réservoirs reservoires.insert(tuyau[0]); } } cout<< reservoires.size() << '\n'; for(int depart:reservoires){ vector<int>connected_maisons = parcours_largeur(reseau, depart); int mini = INT_MAX; for(int i=0; i < connected_maisons.size()-1; i++){ // Trouver le diamètre minimum dans un composant connecté vector<int>w=reseau.getDiametres()[connected_maisons[i]]; int min_diam = *min_element(w.begin(), w.end()); mini=min(min_diam, mini); } int nb=connected_maisons.size(); cout << connected_maisons[0] << " " << connected_maisons[nb-1] << " " << mini << '\n'; } } int main() { int n, p, val; cin >> n >> p; vector<vector<int>> tuyaux(p); for(int i=0; i < p; i++){ for(int j=0; j < 3; j++){ cin >> val; tuyaux[i].push_back(val); } } solution(tuyaux,n); return 0; }
import numpy as np import sys # Construire la matrice d'adjacence pour le graphe class GraphAdjList: def __init__(self, nb_maisons, liasons): self.voisins = [[] for _ in range(nb_maisons)] self.diametres = [[] for _ in range(nb_maisons)] # pour chaque f_i, t_i, d_i for f,t,d in liasons: # ajouter t dans la liste d'adjacence de f self.voisins[f].append(t) # le diamètre entre f et t est d self.diametres[f].append(d) # créer la liste des maisons connectées au maison de départ (depart) def parcours_largeur(reseau, depart): visited = [False]*len(reseau.voisins) pile = [depart] connected = [] while len(pile) > 0: current = pile.pop() if not visited[current]: connected.append(current) visited[current] = True for v in reseau.voisins[current]: pile.append(v) return connected # résoudre le problème def solution(tab, n): reseau = GraphAdjList(n+1, tab) #Stockez tous les noeuds avec des arêtes sortants qui sont des réservoirs reservoires=set() #Stocker tous les noeuds dont les arêtes entrants sont des robinets. robinets=set([tuyau[1] for tuyau in tab]) for elem in tab: if elem[0] not in robinets: # Ajouter des maisons avec uniquement des tuyaux entrants aux réservoirs reservoires.add(elem[0]) print(len(reservoires)) for reserv in reservoires: connected_maisons = parcours_largeur(reseau, reserv) mini = sys.maxsize for i in range(len(connected_maisons)-1): #Trouver le diamètre minimum dans un composant connecté w=reseau.diametres[connected_maisons[i]] min_diam = np.min(w) mini=min(min_diam,mini) print("{} {} {}".format(connected_maisons[0],connected_maisons[-1], mini)) n,p = map(int, sys.stdin.readline().strip().split()) tuyaux=[] for i in range(p): tuyaux.append(list(map(int, sys.stdin.readline().strip().split()))) solution(tuyaux,n)