POJ 2114: Boatherds
Description
Boatherds Inc. est une entreprise de navigation opérant dans le pays de Trabantustan, offrant des promenades en bateau sur les rivières trabantianes. Toutes les rivières prennent leur source dans les montagnes et se rejoignnet progressivement pour former une seule rivière qui se jette finalement dans la mer. Les villages trabantians sont exactement aux sources, aux jonctions et à l'embouchure de la plus grande rivière. Notez que plus de deux rivières peuvent se rejoindre à une jonction. Cependant, les rivières forment toujours un arbre (avec les villages comme sommets).
La politique de tarification de Boatherds est très simple : chaque segment de chaque rivière entre deux villages est attribué un prix (le prix est le même dans les deux directions), donc si un touriste demande un trajet entre deux villages, les employés du guichet additionnent simplement les prix des segments le long du seul chemin entre les villages.
Un jour, un touriste très étrange est apparu. Elle a dit aux employés qu'elle retournait dans son pays le lendemain et voulait dépenser tout l'argent restant pour une promenade en bateau, ils devaient donc trouver un itinéraire avec ce coût exact. Étant de simples (ahem) hommes d'affaires, ils ont demandé de l'aide aux fabricants de calculatrices Abacus.
Vous êtes donné une description du réseau fluvial avec les coûts des segments de rivière et une séquence d'entiers x1,..., xk. Pour chaque xi, vous devez déterminer s'il existe une paire de villes (a, b) dans le réseau fluvial tel que le coût du trajet entre a et b soit exactement xi. Input
L'entrée consiste en plusieurs instances. Chaque instance est décrite par (dans l'ordre suivant) :
- Une seule ligne contenant un entier unique : le nombre de villages N (1 <= N <= 10 000).
- N lignes décrivant les villages. La i-ème de ces lignes (1 <= i <= N) décrit le village numéro i. Elle contient des entiers séparés par des espaces dj, cj, dj, cj, ..., dk, ck, 0. Les dj sont les numéros des villages d'où les rivières coulent directement vers le village i (sans autres villages entre eux), chaque cj est le prix du trajet entre les villages i et dj. De plus, 2 <= dj <= N et 0 <= cj <= 1 000. Le village 1 correspond toujours à l'embouchure de la plus grande rivière, donc aucun di ne peut jamais être égal à 1.
- M <= 100 lignes décrivant les requêtes. La i-ème de ces lignes correspond à la i-ème requête et contient un entier unique xi (1 <= xi <= 10 000 000).
- L'instance est terminée par une seule ligne contenant le nombre 0.
L'entrée entière est terminée par une seule ligne contenant le nombre 0. Output
Pour chaque instance, vous devez produire une séquence de M lignes (où M est le nombre de requêtes dans l'instance particulière). La i-ème de ces lignes contient le mot "AYE" s'il existe une paire de villes dans le réseau fluvial qui est connectée par un chemin de coût xi, ou le mot "NAY" sinon.
La sortie pour chaque instance doit être suivie d'une seule ligne cotnenant juste le caractère point. Exemple d'entrée
6
2 5 3 7 4 1 0
0
5 2 6 3 0
0
0
0
1
8
13
14
0
0
Exemple de sortie
AYE
AYE
NAY
AYE
.
Le problème consiste à déterminer s'il existe un chemin d'une longueur donnée k dans un arbre.
Pour résoudre ce problème, nous utilisons une méthode de décomposition d'arbre et de diviser pour régner. Voici un exemple de code en C++ qui implémente cette solution :
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 10000;
int n, m, k, ans;
vector<pair<int, int>> adj[MAXN];
bool used[MAXN];
int dist[MAXN], size[MAXN], limit[MAXN];
void dfs_size(int u, int f) {
size[u] = 1;
limit[u] = 0;
for (auto [v, w] : adj[u]) {
if (!used[v] && v != f) {
dfs_size(v, u);
size[u] += size[v];
limit[u] = max(limit[u], size[v]);
}
}
}
int find_root(int u, int f, int root_size) {
int min_limit = INT_MAX, root = -1;
for (auto [v, w] : adj[u]) {
if (!used[v] && v != f) {
if (root_size - size[v] > limit[v]) {
limit[v] = root_size - size[v];
}
if (limit[v] < min_limit) {
min_limit = limit[v];
root = v;
}
int new_root = find_root(v, u, root_size);
if (new_root != -1) {
return new_root;
}
}
}
if (min_limit == INT_MAX) {
return u;
}
return root;
}
void dfs_dist(int u, int f, int d) {
dist[u] = d;
for (auto [v, w] : adj[u]) {
if (!used[v] && v != f) {
dfs_dist(v, u, d + w);
}
}
}
int count_pairs(int u, int f, int d) {
int cnt = 0;
dfs_dist(u, f, d);
sort(dist, dist + n);
int i = 0, j = n - 1;
while (i < j) {
if (dist[i] + dist[j] < k) {
i++;
} else if (dist[i] + dist[j] > k) {
j--;
} else {
if (dist[i] == dist[j]) {
cnt += (j - i + 1) * (j - i) / 2;
break;
}
int st = i, ed = j;
while (st < j && dist[st] == dist[i]) st++;
while (ed > i && dist[ed] == dist[j]) ed--;
cnt += (st - i) * (j - ed);
i = st;
j = ed;
}
}
return cnt;
}
void solve(int u) {
dfs_size(u, -1);
int root = find_root(u, -1, size[u]);
used[root] = true;
ans += count_pairs(root, -1, 0);
for (auto [v, w] : adj[root]) {
if (!used[v]) {
ans -= count_pairs(v, -1, w);
solve(v);
}
}
}
int main() {
while (cin >> n && n) {
for (int i = 0; i < n; ++i) {
adj[i].clear();
used[i] = false;
}
for (int i = 0; i < n; ++i) {
int u = i;
while (true) {
int v, w;
cin >> v;
if (v == 0) break;
cin >> w;
adj[u].push_back({v - 1, w});
adj[v - 1].push_back({u, w});
}
}
while (cin >> k && k) {
ans = 0;
solve(0);
if (ans > 0) {
cout << "AYE\n";
} else {
cout << "NAY\n";
}
}
cout << ".\n";
}
return 0;
}