Skip to Content
CTRL K

Distinct Routes

Explicación

El núcleo de la pregunta está en la restricción de que cada teletransportador se puede usar solo UNA VEZ. Cuántas veces podemos empezar en 1 y llegar a n con esta restricción.

Ford–Fulkerson

Ford–Fulkerson es un algoritmo para calcular el flujo máximo desde una fuente hasta un sumidero en un grafo dirigido en el que cada arista tiene una capacidad. Encuentra de forma repetida un camino de la fuente al sumidero que todavía tiene capacidad sin usar (un camino aumentante) y empuja flujo por él hasta que no existe ningún camino de ese tipo.

Si todas las capacidades de las aristas son enteras, Ford–Fulkerson garantiza que el flujo total hallado es máximo.

Solución

Cada día corresponde a un camino de la habitación 1 a la habitación n. Como cada teletransportador se puede usar solo una vez, dos caminos no pueden compartir el mismo teletransportador.

Modelamos el juego como una red de flujo:

  • Las habitaciones son nodos
  • Los teletransportadores son aristas dirigidas con capacidad = 1
  • La habitación 1 es la fuente, la habitación n es el sumidero

El problema se reduce a hallar el número máximo de caminos disjuntos en aristas de 1 a n, que es exactamente el flujo máximo de esta red.

Con Ford–Fulkerson, cada camino aumentante exitoso representa un día jugable. Cuando ya no existen caminos aumentantes, el flujo total es igual al número máximo de días que se pueden jugar. Luego se pueden reconstruir las aristas usadas para imprimir las rutas reales.

Implementación

Complejidad temporal: O(F⋅(N+M))\mathcal{O}(F \cdot (N + M)), donde FF es el flujo máximo (número de días).

 
 
#include <bits/stdc++.h>
using namespace std;
 
int n, m, vis[505], cap[505][505], og[505][505];
vector<int> adj[505];
 
// BeginCodeSnip{DFS with Flow}
bool dfs(int u) {
	vis[u] = 1;
	if (u == n) return true;
	for (int v : adj[u]) {
		if (cap[u][v] && !vis[v]) {  // If capacity exists and not visited
			if (dfs(v)) {
				cap[u][v]--;  // Reduce forward capacity
				cap[v][u]++;  // Increase backward capacity
				return true;
			}
		}
	}
	return false;
}
 
// EndCodeSnip
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);       // Add reverse edge for flow algorithm
		cap[u][v] = og[u][v] = 1;  // Mark capacity and original edge
	}
 
	int k = 0;
	while (true) {
		memset(vis, 0, sizeof(vis));
		if (!dfs(1)) break;
		k++;
	}
 
	cout << k << "\n";
	while (k--) {
		vector<int> path;
		int curr = 1;
		while (true) {
			path.push_back(curr);
			if (curr == n) break;
			for (int v : adj[curr]) {
				// If edge existed originally AND is currently used (capacity 0)
				if (og[curr][v] && cap[curr][v] == 0) {
					og[curr][v] = 0;  // Mark as printed so we don't reuse
					curr = v;
					break;
				}
			}
		}
		cout << path.size() << "\n";
		for (int p : path) cout << p << " ";
		cout << "\n";
	}
}
Fundamentos