Note de curs, probleme algoritmică, 16 decembrie 2013
În acest curs am implementat problema 1463 - Happiness to People!.
Cerință
Dându-se un arbore cu muchii ponderate (cu costuri) și cu noduri ponderate (cu costuri) să se calculeze cel mai lung drum dintre două noduri din întreg arborele.
Rezolvare
Rezolvarea acestei probleme a fost discutată anterior: Note de curs, probleme algoritmică, 2 decembrie 2013
Implementare
Pentru stocarea datelor asociate nodurilor arborelui vom defini o structură și un array de astfel de structuri:
const int MAX_N = 50000; struct Node { int id; int happiness; bool visited; Node* father; int bestRoad; int bestHappiness; int secondRoad; Node* firstSon; Node* secondSon; }; Node vertexes[MAX_N + 1];
Pentru stocarea structurii arborelui vom folosi liste de adiacență. Vom defini o structură (cu constructor) care să stocheze date despre fiecare muchie. Listele de adiacență vor fi stocate într-un array de vectori de astfel de structuri.
struct Edge { Node* neighbour; int happiness; Edge (Node* neighbour, int happiness) { this->neighbour = neighbour; this->happiness = happiness; } }; vector <Edge> edges[MAX_N + 1];
Pentru stocarea ordinii de parcurgere a nodurilor și a drumului soluție vom defini variabilele:
Node* order[MAX_N]; // nodurile ordonate int answer; // lungimea celui mai lung drum Node* answerNode; // nodul cu cea mai mica adancime care face parte din drum Node* answerRoad[MAX_N]; // nodurile prin care trece cel mai lung drum
Citirea datelor și construirea structurii arborelui (ca graf neorientat):
scanf("%d %d", &n, &m); for (i = 1; i <= n; i++) { scanf("%d", &vertexes[i].happiness); vertexes[i].id = i; } for (i = 1; i <= m; i++) { scanf("%d %d %d", &a, &b, &c); edges[a].push_back(Edge(&vertexes[b], c)); edges[b].push_back(Edge(&vertexes[a], c)); }
Ordonarea nodurilor "de jos în sus" se va realiza printr-o parcurgere în lățime (pornind din nodul 1 - ales arbitrar) inversată:
queue<Node*>* bfsQueue = new queue<Node*>(); bfsQueue->push(&vertexes[1]); vertexes[1].visited = true; int counter = 0; while (!bfsQueue->empty()) { Node *node, *son; node = bfsQueue->front(); order[counter++] = node; for (i = 0; i < (int)edges[node->id].size(); i++) { son = edges[node->id][i].neighbour; if (!son->visited) { son->father = node; bfsQueue->push(son); son->visited = true; } } bfsQueue->pop(); } reverse(order, order + n);
Aplicând formulele, calculăm valorile celor 3 funcții și, implicit, soluția problemei. În plus, vom memora și fiii pe care trebuie mers pentru a putea reconstiti soluția:
for (i = 0; i < n; ++i) { Node* node = order[i]; node->bestRoad = node->happiness; node->secondRoad = node->happiness; node->firstSon = NULL; node->secondSon = NULL; for(j = 0; j < (int)edges[node->id].size(); j++) { Node* son = edges[node->id][j].neighbour; int happiness = edges[node->id][j].happiness; if (son->father != node) { if (node->bestRoad < node->happiness + happiness + son->bestRoad) { node->secondRoad = node->bestRoad; node->secondSon = node->firstSon; node->bestRoad = node->happiness + happiness + son->bestRoad; node->firstSon = son; } else if (node->secondRoad < node->happiness + happiness + son->bestRoad) { node->secondRoad = node->happiness + happiness + son->bestRoad; node->secondSon = son; } } } node->bestHappiness = node->bestRoad + node->secondRoad - node->happiness ; if (answer < node->bestHappiness) { answer = node->bestHappiness; answerNode = node; } }
Folosind datele suplimentare calculate anterior, reconstituim soluția:
counter = 0; for (Node* node = answerNode; node->firstSon != NULL; node = node->firstSon) { answerRoad[counter++] = node; } reverse(answerRoad, answerRoad + counter); if (answerNode->secondSon != NULL) { for (Node* node = answerNode->secondSon; node->firstSon != NULL; node = node->firstSon) { answerRoad[counter++]= node; } }
Tot ceea ce mai lipsește este afișarea drumului optim în formatul cerut de problemă.