Skip to Content
CTRL K

Mooriokart

Editorial oficial (C++) 

Pista

El grafo es un bosque, y solo se nos permite elegir un camino de cada árbol para alcanzar nuestro total. ¡Esto parece una mochila (knapsack)!

El problema de escribir una mochila de forma directa es que no hay cota sobre cuán largo podemos hacer nuestro camino. Observemos que todas las pistas y caminos de longitud ≥Y\ge Y se comportan igual porque ya son lo suficientemente largos. ¿Cómo puede esto simplificar nuestra DP?

Explicación

La observación clave es que podemos comprimir todos los caminos y pistas de longitud ≥Y\ge Y porque todos se tratan igual, en el sentido de que resultan en una pista de longitud suficiente.

Para cada árbol, podemos comprimir todos los caminos en pares (longitud,frecuencia)(longitud, frecuencia). Luego, podemos hacer mochila como de costumbre. Sin embargo, nótese que como estamos comprimiendo todos los caminos de longitud ≥Y\ge Y, necesitamos almacenar explícitamente también la suma de las longitudes de los caminos.

Nuestro estado de DP llevaría registro tanto de la suma de las longitudes de los caminos como del número de tales caminos, para cada longitud posible de nuestro camino.

Sea kk el número de árboles en nuestro bosque. Para tener en cuenta las posibles formas de ordenar nuestros caminos, necesitamos multiplicar nuestra suma inicial de caminos por 2k∗k!2^{k} * k!. Sin embargo, las rotaciones cíclicas y los caminos invertidos se consideran iguales, así que dividimos por 2k2k: 2k−1∗(k−1)!2^{k - 1} * (k - 1)!.

Implementación

Complejidad temporal: O(NY32)\mathcal{O}(NY^{\frac{3}{2}})

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const int MOD = 1e9 + 7;
 
int main() {
	freopen("mooriokart.in", "r", stdin);
	int n, m, x, y;
	cin >> n >> m >> x >> y;
	vector<vector<array<int, 2>>> adj(n);
	for (int i = 0; i < m; i++) {
		int u, v, d;
		cin >> u >> v >> d;
		adj[--u].push_back({--v, d});
		adj[v].push_back({u, d});
	}
 
	vector<bool> vis(n);
	vector<int> tree_nodes;
	function<void(int, int)> get_tree_nodes = [&](int u, int p) {
		vis[u] = true;
		tree_nodes.push_back(u);
		for (auto [v, w] : adj[u]) {
			if (v == p) { continue; }
			get_tree_nodes(v, u);
		}
	};
 
	// path_info[len] = {sum of path lengths, # of paths}
	map<int, array<int, 2>> path_info;
	function<void(int, int, int, int)> calc_path_info = [&](int u, int p, int d,
	                                                        int s) {
		for (auto [v, w] : adj[u]) {
			if (v == p) { continue; }
			if (v < s) {
				auto &[sum, freq] = path_info[min(y, d + w)];
				sum = (sum + d + w) % MOD;
				freq++;
			}
			calc_path_info(v, u, d + w, s);
		}
	};
 
	// dp[path_len] = {len_sum, num_paths}
	vector<array<ll, 2>> dp(y + 1);
	int k = n - m;
	dp[min(y, k * x)] = {k * x, 1};
	for (int i = 0; i < n; i++) {
		if (vis[i]) { continue; }
		get_tree_nodes(i, -1);
		for (int v : tree_nodes) { calc_path_info(v, -1, 0, v); }
 
		vector<array<ll, 2>> new_dp(y + 1);
		for (auto [val, arr] : path_info) {
			const auto [sum, freq] = arr;
			for (int j = 0; j <= y; j++) {
				int nxt = min(y, j + val);
				new_dp[nxt] = {(new_dp[nxt][0] + dp[j][1] * sum + dp[j][0] * freq) %
				                   MOD,
				               (new_dp[nxt][1] + dp[j][1] * freq) % MOD};
			}
		}
 
		tree_nodes.clear();
		path_info.clear();
		dp = move(new_dp);
	}
 
	for (int i = 1; i < k; i++) { dp[y][0] = (dp[y][0] * 2 * i) % MOD; }
 
	freopen("mooriokart.out", "w", stdout);
	cout << dp[y][0] << endl;
}
Fundamentos