Per il server centrale di questo istituto transitano tutte le connessioni ad internet, che, a quanto pare, stanno intasando tutta la rete. Il docente responsabile, quindi, sta procedendo con un’indagine per capire quali sono le cause di questi rallentamenti.
La rete della scuola è strutturata ad albero, in cima si trova il server centrale che è collegato a dei server periferici, i quali a loro volta possono essere collegati ad altri server, ecc. Ognuno di questi server viene definito “nodo di articolazione” se è collegato direttamente ad almeno un altro nodo di articolazione. I server che non sono collegati a nessun altro (le foglie dell’al— bero) sono i computer di un laboratorio e sono proprio quelli che utilizzano la banda!
A tutti i nodi di articolazione è associato un peso che rappresenta il valore massimo che può sopportare prima di causare problemi, a tutti gli altri nodi invece è associato un peso che rappresenta l’utilizzo medio della banda in quel laboratorio.
La banda passante per un nodo di articolazione viene calcolata sommando la banda passante di tutti i nodi di articolazione collegati in quel nodo più la banda dei laboratori direttamente collegati. Un nodo di articolazione da problemi se la banda passante è maggiore o uguale alla banda massima supportata.
Scrivere quindi un programma che, dato in input la rete della scuola, calcoli il numero dei nodi di articolazione che causano problemi.
Input
Il programma deve leggere da un file di nome ‘input.txt’. Nella prima riga sono presenti due interi separati da uno spazio: N e S, rispettivamente il numero di server in rete (compreso il server centrale e i server del laboratorio) e il numero del server centrale. Nelle successive N righe sono presenti due interi i, j.
i è il numero del server a cui il server corrente è collegato, j è la banda massima se è un nodo di articolazione, la banda media se è un server di un laboratorio.
Output
Il programma deve scrivere in un file di nome ‘output/cxt’. Deve venire stampato un unico intero, la soluzione del problema.
Assunzioni
0 < N <= 100.000
0 <= S < N
0 <= i < N
1<= j <= 1.000.000
Il server S è collegato a S
Nell’esempio i nodi 3 e 4 causano problemi:
input.txt output.txt
5 4 2
4 1
3 2
3 2
4 1
4 2
Questo è un classico problema ad albero: partendo dalle foglie (i computer che consumano banda) scriviamo il consumo nei padri, che lo scriveranno ai loro padri tramite una funzione ricorsiva.
Alla fine contando i nodi in cui il consumo supera la banda avremo la soluzione.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include<cstdlib> #include<iostream> #include<fstream> #include<vector> #include<cstring> #define N 100000 using namespace std; ifstream in; ofstream out; struct nodo{ int banda; int padre; int consumo;}; int n,s,p=0,t,size; nodo pc[N]; int figli[N]; void pa(int k){if (k==s) return; pc[pc[k].padre].consumo+=pc[k].banda; pa(pc[k].padre);} int main(){ in.open("input.txt"); out.open("output.txt"); in>>n>>s; memset(figli,0,n); for (int i=0;i<n;i++){ in >>t>>pc[i].banda; figli[t]++; pc[i].padre=t; pc[i].consumo=0;} for (int i=0;i<n;i++){ // scrivi nel padre il consumo if (figli[i] ==0){//foglia pc[pc[i].padre].consumo+=pc[i].banda; pa(pc[i].padre); }} for (int i=0;i<n;i++) if (pc[i].consumo > pc[i].banda) p++; out<<p; return 0;} |
