Introducción al algoritmo sap
C se puede lograr si la complejidad del tiempo se puede reducir cada vez que se encuentra la ruta incremental. Por marcador de distancia nos referimos al número mínimo de arcos desde un punto hasta el sumidero (otro marcador de distancia es el número mínimo de arcos desde el punto fuente hasta el punto, lo que esencialmente no hace ninguna diferencia). Supongamos que la etiqueta del punto i es D [i], entonces el arco (i, j) que satisface D [i] = D [j] +1 se llama arco permitido. Al ampliarse, solo se puede usar el arco permitido. lograr el efecto "¿Cómo ir?". La etiqueta inicial de cada punto se puede obtener a partir de la convergencia a lo largo de todos los bordes inversos a través de BFS al principio. En aplicaciones prácticas, la etiqueta de distancia de todos los puntos se puede establecer inicialmente en 0. La pregunta es cómo mantener la distancia durante el ensanchamiento. Etiqueta de proceso.
El método para mantener el etiquetado de distancia es el siguiente: cuando se descubre que un punto de partida no permite arcos en el proceso de búsqueda de una carretera ensanchada, el etiquetado de distancia de este punto se establece hasta el final. punto de todos los arcos, comenzando desde él Sume uno al valor mínimo de la etiqueta de distancia inicial. No quiero demostrar si este enfoque para marcar la distancia es correcto. Debido a los marcadores de distancia y porque "cualquier camino es el camino más corto", puede usar DFS para encontrar el camino ensanchado y usar la pila para guardar el arco del camino actual. Cuando el marcador de distancia de un punto cambia, el arco en la pila que apunta a él ya no debe ser un arco permitido, así que déjelo salir de la pila y continúe ensanchándose usando el punto final del arco en la parte superior de la pila. Otra forma de optimizar la constante es establecer el arco actual en el arco que proporcione la marca más pequeña al cambiar la marca de distancia. La razón por la que el arco actual está escrito correctamente es que siempre podemos asegurarnos de que no haya ningún arco permitido precediendo al arco actual en la lista de adyacencia.
Otra área de optimización constante es que, basándose en la idea del algoritmo Dinic, después de encontrar y expandir cada camino, ya no retiramos todos los vértices del camino, sino solo el cuello de botella. borde y sus lados posteriores. Cabe señalar que en cualquier momento, el "punto actual" a expandir debe ser el final del punto superior de la pila. De hecho, este es un proceso de optimización continuo y, debido a la estructura de los bordes actuales, ciertamente podemos recuperar todos los bordes en la ruta anterior al cuello de botella en un tiempo O (n).