La razón por la que su programa excede el límite de tiempo es porque para cada consulta realiza cálculos O (N). Solo por eso, la complejidad del tiempo es al menos O (NK), y eso es suficiente para exceder el límite de tiempo.
La idea para la solución de este problema es que no necesita reconstruir los gráficos para cada consulta. Si los dos vértices están conectados en un punto, la distancia de Manhattan entre los dos vértices es constante, independientemente del borde que se agregue más adelante. Por lo tanto, responder una consulta se reduce a responder las siguientes dos preguntas.
1. ¿Están los dos vértices conectados en el momento consultado?
2. ¿Cuál es la distancia de Manhattan entre los dos puntos después de que el gráfico está completamente conectado?
La primera pregunta se puede responder utilizando la estructura de conjuntos disjuntos (union-find), fusionando los conjuntos de dos vértices después de agregar cada borde. La segunda pregunta puede responderse simplemente atravesando el árbol (el problema dice que el gráfico es un árbol) y calculando las diferencias relativas en las dos coordenadas.
- ¿Existen constructores de algoritmos comerciales Plug and Play que no requieren ninguna habilidad de codificación?
- Dado un gráfico bipartito, ¿cómo puedo encontrar su subgrafo que es un gráfico bipartito completo y tiene la mayor cantidad de vértices?
- Cómo averiguar la complejidad temporal de un algoritmo dado
- Cómo resolver la pregunta en la descripción a continuación
- ¿Cuáles son algunas aplicaciones del mundo real en las que es útil el aprendizaje incremental de algoritmos (aprendizaje automático)? ¿Se prefieren las SVM para tales aplicaciones?
hyun-min-choi / 1984.cpp
Este es mi código para el problema.
