Les graphes en couches sont une structure intéressante que j'ai découverte récemment lors d'une simulation de compétition. Initialement peu familière, j'ai maintenant une meilleure compréhension de ce concept.

Ma compréhension personnelle des graphes en couches : les arêtes du graphes peuvent changer d'état à des moments spécifiques. Pour modéliser cela, nous créons des couches du graphes correspondant à différents états temporels.

En substance, il s'agit de stocker les différents états des arêtes. Lors de la connexion des nœuds, les nœuds de la même couche peuvent être connectés, et des connexions peuvent églaement être établies entre des couches différentes.

On comprend alors que la difficulté des graphes en couches réside dans leur construction. Il faut être attentif à la manière de connecter les nœuds entre différentes couches. Le reste consiste simplement à appliquer des algorithmes standards de plus court chemin.

Une autre considération importante est la gestion de l'espace de stockage. Il est préférable d'allouer jusqu'à 1e6 d'espace pour être sûr de disposer de suffisamment de mémoire, car le nombre d'arêtes peut devenir considérable lorsque l'on connecte des nœuds entre différentes couches.

Puisque la visualisation de tels graphes est complexe, il est utile de se concentrer mentalement sur le concept de "couches".

Problème type :

1. Sur Luogu : P2939 [USACO09FEB] Revamping Trails G

Lors de la construction du graphe, nous créons k couches pour représenter les différentes situations sous différents autoroutes.

Pour les arêtes dans la même couche, nous calculons leur numéro correspondant, conservant le même poids d'arête et les connectons directement.

Pour les arêtes entre couches différentes, nous connectons la couche i vers la couche i+1, ce qui représente l'utilisation d'un autre autoroute qui annule le poids de l'arête.

for i in range(0, k+1):
    ajouter(i * n + x, i * n + y, z)
    ajouter(i * n + y, i * n + x, z)
    
for i in range(0, k):
    ajouter(i * n + x, (i + 1) * n + y, 0)
    ajouter(i * n + y, (i + 1) * n + x, 0)

Ensuite, pour chaque couche de nœuds, il suffit d'exécuter un algorithme de plus court chemin.

import sys
import heapq

inf = 10**9
N = 10**5 + 10
M = 5*10**5 + 10

n, m, k = 0, 0, 0
vis = [0] * (N * 30)
ans = [inf] * (N * 30)
idx = 0
head = [0] * (N * 30)
e = [0] * (M * 30)
w = [0] * (M * 30)
nxt = [0] * (M * 30)

def ajouter(x, y, z):
    global idx
    idx += 1
    e[idx] = y
    w[idx] = z
    nxt[idx] = head[x]
    head[x] = idx

def dijkstra():
    ans[1] = 0
    heap = []
    heapq.heappush(heap, (0, 1))
    
    while heap:
        dist, x = heapq.heappop(heap)
        if vis[x]:
            continue
        vis[x] = 1
        
        i = head[x]
        while i:
            if ans[e[i]] > ans[x] + w[i]:
                ans[e[i]] = ans[x] + w[i]
                heapq.heappush(heap, (ans[e[i]], e[i]))
            i = nxt[i]

def main():
    global n, m, k
    n, m, k = map(int, sys.stdin.readline().split())
    
    for _ in range(m):
        x, y, z = map(int, sys.stdin.readline().split())
        for i in range(0, k+1):
            ajouter(i * n + x, i * n + y, z)
            ajouter(i * n + y, i * n + x, z)
        for i in range(0, k):
            ajouter(i * n + x, (i + 1) * n + y, 0)
            ajouter(i * n + y, (i + 1) * n + x, 0)
    
    for i in range(1, n * k + n + 1):
        ans[i] = inf
    
    dijkstra()
    
    min_val = inf
    for i in range(0, k+1):
        min_val = min(min_val, ans[i * n + n])
    
    print(min_val)

if __name__ == "__main__":
    main()

En réfléchissant attentivement, les graphes en couches sont une concept vraiment ingénieux.

Autres problèmes pour s'exercer :

P4568 [JLOI2011] Itinéraire de vol

P4822 [BJWC2012] Gelé