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ă.