Dans cet article, nous donnerons des réponses en Python aux sujets # 7 à # 12 du cours ALDS1 (Introduction aux algorithmes et structures de données) du livre en spirale AOJ.
Ceci est une suite de l'article précédent Spiral book in Python, AOJ's answer (ALDS1 # 1 ~ # 6). Veuillez vous référer à cet article pour savoir ce qu'est un livre en spirale / AOJ.
ALDS1_7_A: Rooted Trees
class Node:
def __init__(self, pa=-1, chs=None):
self.pa = pa
self.chs = chs
n = int(input())
tree = {id:Node() for id in range(n)}
for _ in range(n):
id, _, *chs = map(int, input().split())
tree[id].chs = chs
for ch in chs:
tree[ch].pa = id
def set_depths(id, depth):
tree[id].depth = depth
for ch in tree[id].chs:
set_depths(ch, depth+1)
for id in tree:
if tree[id].pa == -1:
set_depths(id, 0)
break
for id, node in tree.items():
kind = "root" if node.pa == -1 else "internal node" if node.chs else "leaf"
print(f"node {id}: parent = {node.pa}, depth = {node.depth}, {kind}, {node.chs}")
--Le nœud est représenté comme une classe Node qui contient une référence à l''id du parent pa et une référence aux enfants'chs à l''id`. Au lieu de référencer tous les enfants, le nœud ne peut être représenté que par la référence à l'enfant le plus à gauche et la référence au frère le plus à droite, et n'importe quel arbre peut être traité comme un arbre virtuellement bifurqué. "Représentation gauche-enfant frère droit" (left-child, right-frère representaiton) ", mais je pense que le code est plus facile à lire s'il utilise une référence à tous les enfants.
L'arbre est représenté sous la forme d'un dictionnaire avec «id» comme clé et l'instance «Node» correspondante comme valeur.
Comme c'est un problème d'afficher le parent comme -1 quand il n'y a pas de parent, -1 est formellement traité comme un identifiant de rien.
ALDS1_7_B: Binary Trees
class Node:
def __init__(self, chs, pa=-1):
self.chs = chs
self.pa = pa
n = int(input())
tree = {id:Node(chs=[-1,-1]) for id in range(-1, n)}
for _ in range(n):
id, *chs = map(int, input().split())
tree[id].chs = chs
for ch in chs:
tree[ch].pa = id
def set_d_and_h(id, d):
tree[id].d = d
h = 0
for ch in tree[id].chs:
if ch != -1:
h = max(h, set_d_and_h(ch, d+1) + 1)
tree[id].h = h
return h
for id in tree:
if tree[id].pa == -1:
set_d_and_h(id, 0)
break
for id, node in tree.items():
if id != -1:
sib = tree[node.pa].chs[1] if tree[node.pa].chs[0] == id else tree[node.pa].chs[0]
deg = 2 - node.chs.count(-1)
kind = "root" if node.pa == -1 else "internal node" if deg else "leaf"
print(f"node {id}: parent = {node.pa}, sibling = {sib}, degree = {deg}, depth = {node.d}, height = {node.h}, {kind}")
Lorsqu'il n'y a pas d'enfants, il est exprimé par -1 et entrée, donc pour faire une boucle sur l'enfant même dans ce cas, ajoutez un nœud dont l''id 'correspond à -1 à l'arbre en tant que soi-disant garde. Il y a. Les informations parent-enfant pour les nœuds avec ʻid` de -1 ne sont jamais utilisées
La profondeur et la hauteur peuvent être calculées de manière récursive, et j'espère qu'elles peuvent être calculées en même temps comme ceci.
ALDS1_7_C: Tree Walk
class Node:
def __init__(self, chs, pa=-1):
self.chs = chs
self.pa = pa
n = int(input())
tree = {id:Node(chs=[-1,-1]) for id in range(-1, n)}
for _ in range(n):
id, *chs = map(int, input().split())
tree[id].chs = chs
for ch in chs:
tree[ch].pa = id
def walk(id, order):
walked = ""
if id != -1:
if order == "Pre":
walked += f" {id}"
walked += walk(tree[id].chs[0], order)
if order == "In":
walked += f" {id}"
walked += walk(tree[id].chs[1], order)
if order == "Post":
walked += f" {id}"
return walked
for id in tree:
if tree[id].pa == -1:
for order in ["Pre", "In", "Post"]:
print(order + "order\n" + walk(id, order))
break
--La partie ci-dessus def walk est la même que la question précédente 7_B
ALDS1_7_D: Reconstruction of a Tree
_ = int(input())
pr_walk = [*map(int, input().split())]
in_walk = [*map(int, input().split())]
walked = []
def recon_tree(pr_walk, in_walk):
if pr_walk:
root = pr_walk[0]
i = in_walk.index(root)
recon_tree(pr_walk[1:i+1], in_walk[:i])
recon_tree(pr_walk[i+1:], in_walk[i+1:])
walked.append(root)
recon_tree(pr_walk, in_walk)
print(*walked)
--Si vous souhaitez simplement afficher la marche Post order, vous pouvez le faire pendant le processus de reconstruction de l'arbre, et vous n'avez pas besoin d'utiliser l'arbre reconstruit, vous n'avez donc pas besoin de créer une instance du nœud.
Dans la liste concaténée, vous pouvez insérer / supprimer (positionné) avec $ O (1) $, mais la recherche coûte $ O (n) $, et vous devez rechercher la suppression par clé, donc $ O (n) Cela coûte $. D'autre part, l'arbre de dichotomie est une structure de données qui vous permet d'insérer, de rechercher et de supprimer tout à $ O (h) $ avec la hauteur de l'arbre comme $ h $. $ h $ est $ O (n) $ dans le pire des cas, mais lorsque vous insérez des éléments aléatoirement pour composer un arbre, il est très rapide à $ O (\ log n) $ en moyenne. La traversée dans l'ordre permet également de visiter les nœuds dans l'ordre de tri des clés à un instant $ \ Theta (n) $.
ALDS1_8_A: Binary Search Tree I Le problème de l'insertion d'éléments dans un arbre de dichotomie. Omis car il est complètement inclus dans le numéro III suivant
ALDS1_8_B: Binary Search Tree II Le problème de l'insertion et de la recherche d'éléments dans l'arbre de dichotomie. Omis car il est complètement inclus dans le numéro III suivant
ALDS1_8_C: Binary Search Tree III Problème d'insertion / recherche / suppression d'éléments dans l'arbre de dichotomie
class Node:
def __init__(self, key, left=None, right=None):
self.key = key
self.left = left
self.right = right
def insert(key):
global root
if root:
ch = root
while ch:
pa, ch = ch, ch.left if key < ch.key else ch.right
if key < pa.key:
pa.left = Node(key)
else:
pa.right = Node(key)
else:
root = Node(key)
def find(key):
node = root
while node and node.key != key:
node = node.left if key < node.key else node.right
print("yes" if node else "no")
def delete(key):
global root
pa, node = None, root
while node.key != key:
pa, node = node, node.left if key < node.key else node.right
if node.left and node.right:
pa, to_del = node, node.right
while to_del.left:
pa, to_del = to_del, to_del.left
node.key = to_del.key
else:
to_del = node
ch = to_del.left or to_del.right
if not pa:
root = ch
elif pa.left == to_del:
pa.left = ch
else:
pa.right = ch
def walk(node, order):
walked = ""
if node:
if order == "Pre":
walked += f" {node.key}"
walked += walk(node.left, order)
if order == "In":
walked += f" {node.key}"
walked += walk(node.right, order)
return walked
def show():
for order in ["In", "Pre"]:
print(walk(root, order))
root = None
cmds = {"print":show, "insert":insert, "find":find, "delete":delete}
for _ in range(int(input())):
cmd_name, *key = input().split()
cmds[cmd_name](*map(int,key))
――L'insertion et la recherche sont comme vous pouvez le voir, c'est facile à comprendre simplement en descendant de la racine à la feuille, mais la suppression est un peu compliquée
None s'il n'y a pas d'enfant) l'enfant du parent du nœud que vous voulez supprimer, pour ainsi dire," si l'enfant hérite de la trace ". Cela est gênant lorsqu'il y a deux enfants sur le nœud que vous souhaitez supprimer. Par exemple, lorsque vous essayez de faire réussir l'enfant de droite, si l'enfant de droite a déjà un enfant de gauche, l'enfant de gauche sera deux. Par conséquent, envisagez de faire réussir un autre nœud. Même après la succession, chaque nœud doit apparaître dans l'ordre de tri dans la patrouille d'ordre intermédiaire, mais cela peut être satisfait en retirant et en remplaçant le nœud immédiatement avant ou après dans la patrouille d'ordre intermédiaire. Ici, le nœud immédiatement après (le point final lorsque le sous-arbre de droite continue d'être tracé vers la gauche) est retiré. Puisqu'il y a au plus un enfant au nœud immédiatement avant (pas d'enfant droit) et immédiatement après (pas d'enfant gauche), retirez-le par la méthode ci-dessus quand il y a au plus un enfant.――Il peut être géré sans avoir les informations du nœud parent dans chaque nœud. L'insertion et la recherche ne nécessitent pas d'informations sur le nœud parent, uniquement lors de la suppression, mais vous pouvez conserver les informations parentales sur le chemin vers le nœud que vous souhaitez supprimer
retourne ʻA si ʻA est vrai, et renvoie B si ʻA est faux.En outre, [Colmen "Algorithm Introduction 3rd Edition"](https://www.amazon.co.jp/dp/B078WPYHGN
Comme indiqué à la fin du chapitre 12 de), cette méthode de suppression peut poser des problèmes. Avec cette méthode de suppression, si le nœud que vous souhaitez supprimer a deux enfants, les informations de clé d'un autre nœud sont copiées dans l'instance du nœud que vous souhaitez supprimer à l'origine, au lieu de supprimer l'instance du nœud que vous souhaitez supprimer à l'origine. Une instance du nœud sera supprimée. Par conséquent, si vous référencez une instance au lieu d'une clé ailleurs dans votre code, vous pouvez faire référence à un nœud différent du nœud prévu. La solution à ce problème, bien que plus compliquée, consiste à réécrire la partie fonction delete dans un formulaire qui n'utilise pas une copie des informations clés:
def trans(pa, node, new_node):
if not pa:
global root
root = new_node
elif pa.left == node:
pa.left = new_node
else:
pa.right = new_node
def delete(key):
pa, node = None, root
while node.key != key:
pa, node = node, node.left if key < node.key else node.right
if node.left and node.right:
pa_heir, heir = node, node.right
while heir.left:
pa_heir, heir = heir, heir.left
if pa_heir != node:
trans(pa_heir, heir, heir.right)
heir.right = node.right
trans(pa, node, heir)
heir.left = node.left
else:
trans(pa, node, node.left or node.right)
ALDS1_8_D: Treap
Un arbre dichotomisé peut être inséré, recherché et supprimé avec la hauteur de l'arbre comme $ h $, le tout avec $ O (h) $, et lors de la construction d'un arbre en insérant des éléments au hasard, $ h $ est en moyenne. $ O (\ log n) $ est très rapide, mais pour le pire ordre d'insertion, ce sera $ O (n) $. Un arbre de recherche dichotomique conçu pour supprimer la valeur attendue ou la pire valeur la plus élevée de la hauteur de l'arbre à $ O (\ log n) $ pour tout ordre d'insertion est appelé un arbre de recherche dichotomique équilibré. Ceci est particulièrement utile pour les algorithmes en ligne où vous ne pouvez pas choisir l'ordre d'insertion.
--L'arbrep est un arbre de dichotomie auquel est assignée au hasard une nouvelle variable, priorité, pour en faire un tas de dichotomie. Cela a pour effet de rendre aléatoire l'ordre d'insertion et la valeur attendue de la hauteur de l'arbre pour tout ordre d'insertion peut être supprimée à $ O (\ log n) $. Cependant, la pire valeur est $ O (n) $
――Les arbres de recherche dichotomiques équivalents qui suppriment fortement la pire valeur de hauteur d'arbre à $ O (\ log n) $ incluent les arbres rouges et noirs (arbres bicolores), mais ils sont plus compliqués.
ALDS1_9_A: Complete Binary Tree
N = int(input())
heap = input().split()
for i in range(N):
print(f"node {i+1}: key = {heap[i]}, ", end="")
print(f"parent key = {heap[(i-1)//2]}, " if i else "", end="")
print(f"left key = {heap[2*i+1]}, " if 2*i+1 < N else "", end="")
print(f"right key = {heap[2*i+2]}, " if 2*i+2 < N else "")
, 2 * i, 2 * i + 1`ALDS1_9_B: Maximum Heap
Si vous écrivez vous-même max_heapify,
def max_heapify(A, i):
triad = {j:A[j] if j < N else -float("inf") for j in [i, 2*i+1, 2*i+2]}
i_max = max(triad, key=triad.get)
if i != i_max:
A[i], A[i_max] = A[i_max], A[i]
max_heapify(A, i_max)
N = int(input())
heap = [*map(int, input().split())]
for i in reversed(range(N//2)):
max_heapify(heap, i)
print("", *heap)
--Dans max_heapify, considérons un triplet du nœud parent spécifié ʻA [i]et ses enfants ʻA [2 * i + 1], ʻA [2 * i + 2]. Un enfant qui n'existe pas est traité comme $ - \ infty $. Si le nœud parent est plus petit que le nœud enfant, remplacez le nœud parent par le nœud enfant le plus grand, puis récursivement max_heapify` sur ce nœud enfant.
max_heapify suit l'enfant, le montant du calcul est de l'ordre de la hauteur d'un demi-arbre complet $ O (\ log N) $. Si vous faites max_heapify pour tous les nœuds, il y a au plus $ N / 2 ^ h $ sous-arbres avec une hauteur de $ h $$ (1 \ le h \ le \ log N) $, donc le tout Le montant du calcul est $ O (N \ sum_ {h = 1} ^ {\ log N} h / 2 ^ h) = O (N) $. Ici, $ \ sum_ {h = 0} ^ \ infty h / 2 ^ h = O (1) $ a été utilisé.Avec le module heapq:
from heapq import heapify
_, heap = input(), [-int(x) for x in input().split()]
heapify(heap)
print("", *[-x for x in heap])
heapq gère le tas minimum, il est marqué négativement pour traiter le tas maximum comme le tas minimum.ALDS1_9_C: Priority Queue
Si j'écris ʻextract ou ʻinsert par moi-même comme ci-dessous, cela devient TLE:
def max_heapify(A, i):
triad = {j:A[j] if j < len(A) else -float("inf") for j in [i, 2*i+1, 2*i+2]}
i_max = max(triad, key=triad.get)
if i != i_max:
A[i], A[i_max] = A[i_max], A[i]
max_heapify(A, i_max)
def extract(A):
print(A[0])
A[0] = A[-1]
A.pop()
max_heapify(A, 0)
def increase_key(A, i, key):
A[i] = key
while i and A[(i-1)//2] < A[i]:
A[(i-1)//2], A[i] = A[i], A[(i-1)//2]
i = (i-1)//2
def insert(A, key):
A.append(None)
increase_key(A, len(A)-1, key)
heap = []
while True:
op, *key = input().split()
if op == "end":
break
if op == "extract":
extract(heap)
else:
insert(heap, int(*key))
Apparemment, il semble que vous deviez inventer beaucoup, donc si vous abandonnez et utilisez le module heapq, cela passera:
from heapq import heappop, heappush
heap = []
while True:
op, *key = input().split()
if op == "end":
break
if op == "extract":
print(-heappop(heap))
else:
heappush(heap, -int(*key))
Il existe deux types de méthodes de planification dynamique: une méthode descendante qui utilise la récurrence mémorielle et une méthode ascendante qui résout explicitement les problèmes partiels dans l'ordre croissant.
――D'un autre côté, la méthode ascendante a l'inconvénient de devoir penser à l'ordre ascendant, mais vous pouvez économiser la quantité de calcul spatial lorsque le résultat du calcul du problème partiel peut être écarté au milieu comme le problème du nombre de Fibonacci ci-dessous. Il y a un mérite qui peut être fait
ALDS1_10_A: Fibonacci Number Dans la méthode descendante:
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return 1
return fib(n-1) + fib(n-2)
print(fib(int(input())))
Dans la méthode ascendante:
x = y = 1
for _ in range(int(input())):
x, y = x + y, x
print(y)
ALDS1_10_B: Matrix Chain Multiplication
Dans la méthode descendante:
from functools import lru_cache
n = int(input())
p = [int(input().split()[0]) for _ in range(n-1)] + [*map(int, input().split())]
@lru_cache(maxsize=None)
def n_mul(i, j):
if j - i == 1:
return 0
return min(n_mul(i,k) + n_mul(k,j) + p[i]*p[k]*p[j] for k in range(i+1,j))
print(n_mul(0, n))
n_mul (i, j) résout le problème partiel $ \ prod_ {k = i} ^ {j-1} A_k $Dans la méthode ascendante:
n = int(input())
p = [int(input().split()[0]) for _ in range(n-1)] + [*map(int, input().split())]
n_mul = [[0]*(n+1) for _ in range(n+1)]
for l in range(2, n+1):
for i in range(n-l+1):
j = i + l
n_mul[i][j] = min(n_mul[i][k] + n_mul[k][j] + p[i]*p[k]*p[j] for k in range(i+1,j))
print(n_mul[0][n])
--Remplir le résultat du calcul n_mul [i] [j] du problème partiel dans l'ordre croissant de la taille $ l = j-i $ du problème partiel.
ALDS1_10_C: Longest Common Subsequence
En Python, la méthode naturelle suivante sera TLE au milieu, que ce soit de haut en bas ou de bas en haut. Montant du calcul des deux temps
Dans la méthode descendante:
import sys
from functools import lru_cache
sys.setrecursionlimit(100000)
for _ in range(int(input())):
x, y = input(), input()
@lru_cache(maxsize=None)
def lcs(i, j):
if i == 0 or j == 0:
return 0
if x[i-1] == y[j-1]:
return lcs(i-1, j-1) + 1
return max(lcs(i-1,j), lcs(i,j-1))
print(lcs(len(x), len(y)))
Au format ascendant:
for _ in range(int(input())):
x, y = input(), input()
l = [[0] * (len(y)+1) for _ in range(len(x)+1)]
for i in range(len(x)):
for j in range(len(y)):
l[i+1][j+1] = l[i][j] + 1 if x[i] == y[j] else max(l[i][j+1], l[i+1][j])
print(l[-1][-1])
Au format ascendantiChacun dans une boucle suriContrel[i+1][:]Je calcule, mais c'est juste avantiRésultat du calcull[i][:]Je ne l'utilise que. pour cette raison,l[i][:]Variables temporairesl[:]Stocker dansiMis à jour à chaque fois, passéiDansl[i][:]En ignorant les valeurs de, la quantité de calcul spatial
def lcs(X, Y):
l = [0] * (len(Y) + 1)
for x in X:
l_pre = l[:]
for j, y in enumerate(Y):
if x == y:
l[j+1] = l_pre[j] + 1
elif l[j+1] < l[j]:
l[j+1] = l[j]
return l[-1]
for _ in range(int(input())):
print(lcs(input(), input()))
Si ce code est réécrit sous la forme ci-dessous sans définir la fonction lcs, il sera TLE même s'il doit avoir le même contenu. Je ne comprends pas pourquoi réécrire la fonction pour la définir réduirait la quantité de calcul. Si quelqu'un peut le comprendre, je vous serais reconnaissant de bien vouloir me le faire savoir.
for _ in range(int(input())):
X, Y = input(), input()
l = [0] * (len(Y) + 1)
for x in X:
l_pre = l[:]
for j, y in enumerate(Y):
if x == y:
l[j+1] = l_pre[j] + 1
elif l[j+1] < l[j]:
l[j+1] = l[j]
print(l[-1])
ALDS1_10_D: Optimal Binary Search Tree
En tant qu'algorithme de recherche de graphe principal qui recherche tous les sommets du graphe le long des arêtes, la recherche de priorité de profondeur (Depth First Search; DFS) qui recherche les sommets visités avec Last In et First Out comme une pile. , Il existe une recherche de priorité de largeur (Breadth First Search; BFS) qui recherche les sommets visités avec First In et First Out comme une file d'attente. Il peut être utilisé indépendamment du fait que le graphe soit dirigé ou non.
ALDS1_11_A: Graph
n = int(input())
A = [[0] * n for _ in range(n)]
for _ in range(n):
u, _, *V = map(int, input().split())
for v in V:
A[u-1][v-1] = 1
for a in A:
print(*a)
--Dans la représentation de liste adjacente, le montant du calcul spatial de $ O (E + V) $ est suffisant, mais il faut le temps du calcul du temps de la recherche de liste pour déterminer s'il existe un côté entre les deux sommets spécifiés. D'autre part, bien que la représentation matricielle adjacente nécessite un montant de calcul spatial de $ O (V ^ 2) $, le calcul du temps de $ O (1) $ est utilisé pour déterminer s'il y a ou non un côté entre les deux sommets spécifiés. Cela ne coûte que très cher.
Dans ce code, la matrice adjacente ʻA` est spécifiquement construite, mais dans ce problème, il semble que les sommets ne soient en fait saisis que dans l'ordre à partir de 1, et cela passe même si le traitement d'entrée / sortie est effectué ligne par ligne sans créer de matrice.
ALDS1_11_B: Depth First Search
n = int(input())
G = [None] * n
for _ in range(n):
u, _, *V = map(int, input().split())
G[u-1] = [v-1 for v in V]
d, f = [None] * n, [None] * n
time = 0
def visit(u):
global time
time += 1
d[u] = time
for v in G[u]:
if not d[v]:
visit(v)
time += 1
f[u] = time
for u in range(n):
if not d[u]:
visit(u)
print(u+1, d[u], f[u])
--Bien que vous puissiez écrire en utilisant la pile, écrire en utilisant une récursive comme celle-ci simplifie le code.
--Les trois types d'états suivants pour chaque sommet
d contient le temps de découverte, mais f est Aucund contient l'heure de découverte et f contient l'heure de finest la somme de $ \ Theta (V) $ et le montant du calcul devisite`. D'un autre côté, «visit» est appelé une fois pour chaque nœud, et le montant du calcul est de l'ordre du nombre de côtés qui sortent de ce nœud, donc la somme pour tous les nœuds est $ \ Theta (E) $.ALDS1_11_C: Breadth First Search
n = int(input())
G = [None] * n
for _ in range(n):
u, _, *V = map(int, input().split())
G[u-1] = [v-1 for v in V]
d = [0] + [-1] * (n-1)
q = [0]
while q:
v = q.pop(0)
for u in G[v]:
if d[u] == -1:
d[u] = d[v] + 1
q.append(u)
for v in range(n):
print(v+1, d[v])
while pour la file d'attente q est $ \ Theta (V) $, ce qui se produit parce que chaque nœud est inséré une fois dans la file d'attente et apparaît comme v, et le nœud interne C'est la somme du montant du calcul de l'instruction for. D'autre part, la quantité de calcul pour chaque instruction for est de l'ordre du nombre de côtés qui sortent de ce nœud v, donc la somme pour tous les nœuds est $ \ Theta (E) $.ALDS1_11_D: Connected Components
n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
s, t = map(int, input().split())
G[s].append(t)
G[t].append(s)
reps = [None] * n
for s in range(n):
if reps[s] is None:
reps[s] = s
q = [s]
while q:
v = q.pop(0)
for u in G[v]:
if reps[u] is None:
reps[u] = s
q.append(u)
for _ in range(int(input())):
s, t = map(int, input().split())
print("yes" if reps[s] == reps[t] else "no")
La décomposition des composants concaténés de graphes non dirigés peut être effectuée avec $ O (V + E) $ en utilisant la recherche de priorité de profondeur ou la recherche de priorité de largeur. Ce code utilise la recherche de priorité de largeur. Dans le cas des graphes orientés, il est un peu plus difficile de se décomposer en composants fortement connectés, qui sont définis par le fait qu'ils peuvent ou non aller et venir entre eux plutôt que dans un sens.
En enregistrant l'élément représentatif du composant de connexion auquel chaque nœud appartient dans reps, si les deux nœuds appartiennent ou non au même composant de connexion est $ O (1) $ si vous voyez si reps est le même. Vous pouvez voir à. Le nœud non visité est "reps" mais "None". En tant que source représentative, le nœud «s» qui a été visité en premier dans le composant de connexion est pris.
ALDS1_12_A: Minimum Spanning Tree
from heapq import heapify, heappop
n = int(input())
G = [[*map(int, input().split())] for _ in range(n)]
heap = [[float("inf"), v] for v in range(n)]
heap[0] = [0, 0]
weights = 0
while heap:
heapify(heap)
w, u = heappop(heap)
weights += w
for i, [w, v] in enumerate(heap):
if 0 <= G[u][v] < w:
heap[i] = [G[u][v], v]
print(weights)
――Le temps de calcul de ces algorithmes dépend de la manière d'implémenter la structure de données utilisée dans chaque algorithme, mais il peut être réalisé de manière linéaire logarithmique par rapport à la taille du graphique. L'algorithme de Kruskal peut atteindre $ O (E \ log V) $ dans certaines implémentations, en fonction de la manière dont il implémente un ensemble de tribus qui s'excluent mutuellement. Selon la façon dont la file d'attente priorisée est implémentée dans l'algorithme de Prim, $ O (E \ log V) $ peut être réalisé en l'implémentant avec un tas de 2 minutes comme ce code. Cela peut être amélioré en $ O (E + V \ log V) $ en utilisant le tas de Fibonacci. Il s'agit d'une amélioration car $ V = O (E) $ plutôt que $ V-1 \ le E $ dans le graphe concaténé. Pour les graphes généraux, $ V = \ Omega (E ^ {1/2}) $, et si $ V $ est $ o (E) $, c'est une vraie amélioration.
--Cependant, dans ce code, en utilisant la représentation de matrice de contiguïté au lieu de la représentation de liste de contiguïté, l'instruction for qui s'étend sur le tas est exécutée pour chaque élément extrait du tas, et la taille du tas est grande. Considérant que le maximum est $ V $, il semble que l'ordre du montant du calcul s'aggrave car il contribue $ O (V ^ 2) $ au montant du calcul.
heapq de python n'implémente pas la fonction dite DecreaseKey qui réduit la valeur d'un nœud tout en conservant la condition du tas, il est donc inévitable de réduire la valeur du nœud et d'appeler heapify à chaque fois. Je récupère la condition du tas, mais comme heapify est $ O (n) $, il est plus lent que DecreaseKey de $ O (\ log n) $. Maintenant, la taille du tas $ n $ est jusqu'à $ V $, et heapify est appelé $ V $ fois, donc la contribution de calcul de heapify est également $ O (V ^ 2) $ au total. .. Pour le moment, heapq a une fonction appelée _siftdown (tas, start_pos, pos) ʻinformellement, et si vous l'utilisez, le tas qui ne satisfait pas la condition de tas car la valeur du nœud dans posest réduite. Vous pouvez récupérer la condition de tas de avec $ O (\ log n) $, mais vous ne l'utilisez pas car il passe avecheapify` même si vous ne vous souciez pas de l'utiliser.--Construisez le tas minimum tas composé du coût supplémentaire de chaque nœud, retirez le nœud avec le coût supplémentaire le plus petit et ajoutez le coût aux poids totaux poids. Afin de mettre à jour le coût supplémentaire des nœuds v adjacents au nœud extrait u, non seulement le coût supplémentaire du nœud extrait w mais également les informations sur le nœud u qui a été extrait sont nécessaires, ils sont donc ajoutés au tas Contient une liste «[w, u]» composée d'un coût supplémentaire «w» et d'un numéro de nœud «u». En Python, les comparaisons de listes sont effectuées sous forme de dictionnaire dans l'ordre à partir du premier composant, ainsi heappop peut récupérer correctement le nœud de coût minimum [w, u].
G [u] [v] est ajouté à chaque nœud v adjacent au nœud extrait ʻu (c'est-à-dire que G [u] [v] ʻest non négatif), v est ajouté. Si le coût est inférieur à «w», mettez à jour le coût supplémentaire de «v» de «w» à «G [u] [v]»--Bien qu'il ne puisse pas être utilisé avec AOJ, dans un environnement où scipy peut être utilisé tel qu'AtCoder, l'arborescence de la surface totale minimale peut être obtenue en utilisant la fonction scipy.sparse.csgraph.minimum_spanning_tree () sans écrire le code vous-même.
ALDS1_12_B: Single Source Shortest Path I ALDS1_12_C: Single Source Shortest Path II
Ces deux problèmes sont les mêmes à l'exception de la taille d'entrée et de la limite de temps. Le problème du chemin le plus court du point de départ unique est défini pour un graphe orienté pondéré, et il n'y a pas de solution lorsqu'il existe un chemin fermé négatif (chemin fermé où la somme des poids est négative) qui peut être atteint à partir du point de départ.
--Si le graphe est connu pour être non circulaire ou DAG, il n'y a pas de clôture négative. Dans ce cas, le montant du calcul peut être réduit à $ O (V + E) $ en utilisant le tri topologique.
Je ne sais pas si ce problème est non circulaire, mais je sais que tous les poids sont non négatifs, donc je le résolve avec l'algorithme de Dijkstra. L'algorithme de Dijkstra est similaire à l'algorithme de Prim de l'arborescence de l'aire entière minimale précédente, et détermine le chemin le plus court et sa distance $ d $ dans l'ordre du sommet le plus proche du point de départ avec la distance $ d $. Chaque fois qu'elle est confirmée, la distance $ d $ de chaque sommet qui contient chaque côté qui sort du sommet confirmé est mise à jour si elle peut être mise à jour prochainement.
Dans le code suivant, qui est très similaire au code de l'algorithme de Prim pour le problème d'arborescence de l'aire entière minimale ci-dessus, je peux être résolu mais II devient TLE:
from heapq import heapify, heappop
n = int(input())
G = [None] * n
for _ in range(n):
u, k, *vc = map(int, input().split())
G[u] = {vc[2*i]:vc[2*i+1] for i in range(k)}
d = [None] * n
heap = [[float("inf"), v] for v in range(n)]
heap[0] = [0, 0]
while heap:
heapify(heap)
d_u, u = heappop(heap)
d[u] = d_u
for i, [d_v, v] in enumerate(heap):
if v in G[u]:
d_v_new = d_u + G[u][v]
if d_v > d_v_new:
heap[i] = [d_v_new, v]
for v in range(n):
print(v, d[v])
Le problème est que la partie $ O (V ^ 2) $ exécute l'instruction for dans le tas pour chaque nœud ʻu` récupéré du tas.
for sur le tas à l'instruction for sur la liste de contiguïté, mais je ne sais pas où le nœud adjacent v est stocké dans le tas, et le poids v $ d $ fonctionne bien. Ne peut pas être mis à jour petit. Puisque le tas python utilise une liste au lieu de OrderedDict etc. et qu'il en coûte $ O (n) $ pour rechercher une valeur, il est nécessaire de rechercher chaque fois où le nœud adjacent v est stocké dans le tas. Le montant du calcul ne diminue pas après toutv contenu dans le tas, et j'ai décidé d'ajouter le nœud mis à jour v avec un petit poids au tas en poussant à chaque fois. Le tas contiendra plusieurs nœuds identiques avec des poids différents, mais comme il s'agit du plus petit tas, il sera extrait du nœud le plus léger ajouté le plus récemment. Puisque les nœuds qui n'ont pas pu être supprimés et qui ont été retirés à partir de la deuxième fois ont un poids plus lourd que lorsqu'ils ont été retirés la première fois, la partie ʻif d [v]> d_vne devient pasTrue` et ne fait rien de particulier. Sans dangerSur la base de ce qui précède, si vous réécrivez comme ci-dessous, II passera également:
from heapq import heappop, heappush
n = int(input())
G = [None] * n
for _ in range(n):
u, k, *vc = map(int, input().split())
G[u] = {vc[2*i]:vc[2*i+1] for i in range(k)}
d = [0] + [float("inf")] * (n-1)
heap = [[0, 0]]
while heap:
d_u, u = heappop(heap)
for v in G[u]:
d_v = d_u + G[u][v]
if d[v] > d_v:
d[v] = d_v
heappush(heap, [d[v], v])
for v in range(n):
print(v, d[v])
scipy.sparse.csgraph.dijkstra () sans écrire vous-même le code de l'algorithme de Dijkstra.