Était en discussion https://togetter.com/li/776049
L'utilisez-vous correctement selon le format d'entrée?
https://www.hamayanhamayan.com/entry/2018/09/17/163004
Chaque fois que vous connectez un nœud, les choix se développent et vous voulez toujours sélectionner le plus petit. → Utilisez une file d'attente prioritaire (heapq).
Lorsqu'un taple est passé à heapq, la valeur minimale est déterminée par le premier élément.
O(ElogV)。 Est-ce plus rapide avec le tas de Fibonacci?
https://algo-logic.info/prim-mst/
Méthode Prim
import heapq
def main():
n = int(input())
next = [] #Liste de gestion des contiguïtés
for _ in range(n):
l = list(map(int, input().split()))
next.append([(c, i) for i, c in enumerate(l) if c != -1])
visited = [0] * n
connection = 0
q = [(0, 0)] # (cost, v)
heapq.heapify(q)
ans = 0
while len(q):
cost, v = heapq.heappop(q)
if visited[v]:
continue
#Connectez-vous avec ce nœud
visited[v] = 1
connection += 1
ans += cost
#Mettre en file d'attente où vous pouvez aller à partir du nœud nouvellement connecté
for i in next[v]:
heapq.heappush(q, i)
#Quitter lorsque tous les nœuds sont connectés
if connection == n:
break
print(ans)
return
1 → Trier en fonction du coût du côté. Utilisez la technique du tri par le premier élément lorsque chaque élément de la liste est tabulé et trié. 2 → "Closing the road" = "Créer un côté où les deux points sont déjà connectés", vérifiez donc avec l'arbre Union Find.
O(ElogV)。
https://algo-logic.info/kruskal-mst/
Méthode Clascal
def main():
V, E = map(int, input().split())
uf = UnionFind(V)
#Processus de 1
edges = []
for _ in range(E):
s, t, w = map(int, input().split())
edges.append((w, s, t))
edges.sort()
#Processus 2
cost = 0
for edge in edges:
w, s, t = edge
if not uf.same(s, t):
cost += w
uf.union(s, t)
print(cost)
return
Post-scriptum (6/1)
ARC076 D - Built? Premièrement: pensez à réduire E à l'avance s'il est énorme. → Cette fois, nous avons utilisé que les villes qui ne sont pas adjacentes les unes aux autres sur les coordonnées x et y ne sont pas sélectionnées. Deuxièmement: si les deux axes x et y correspondent à des villes adjacentes, ils seront comptés deux fois, mais je m'en fiche.
def main():
N = int(input())
nodes = []
for i in range(N):
x, y = map(int, input().split())
nodes.append((x, y, i)) #Si les coordonnées sont uniques, vous pouvez les mettre dans Union Find sous forme de taples, mais comme il y a des cas où il y a des villes aux mêmes coordonnées, numérotez-les.
uf = UnionFind(N)
nodes_sorted_by_x = sorted(nodes)
nodes_sorted_by_y = sorted(nodes, key=lambda i: i[1])
edges = []
for i in range(N - 1):
dx = abs(nodes_sorted_by_x[i][0] - nodes_sorted_by_x[i + 1][0])
dy = abs(nodes_sorted_by_x[i][1] - nodes_sorted_by_x[i + 1][1])
cost = min(dx, dy)
edges.append((cost, nodes_sorted_by_x[i][2], nodes_sorted_by_x[i + 1][2]))
for i in range(N - 1):
dx = abs(nodes_sorted_by_y[i][0] - nodes_sorted_by_y[i + 1][0])
dy = abs(nodes_sorted_by_y[i][1] - nodes_sorted_by_y[i + 1][1])
cost = min(dx, dy)
edges.append((cost, nodes_sorted_by_y[i][2], nodes_sorted_by_y[i + 1][2]))
edges.sort()
ans = 0
for edge in edges:
w, s, t = edge
if not uf.same(s, t):
ans += w
uf.union(s, t)
print(ans)
Appendix
Spécifie la clé pour trier la liste des taples.
#Généralement trié par le premier élément du taple.
sortedByFirstKey = sorted(listOfTuple)
#Spécifiez une expression lambda pour Key afin qu'elle trie par le deuxième élément du taple.
sortedBySecondKey = sorted(listOfTuple, key=lambda i: i[1])
# reverse
sortedBySecondKey = sorted(listOfTuple, key=lambda i: i[1], reverse=True)
Surtout lorsque vous essayez de trier la liste des dictionnaires, une erreur se produit, il est donc nécessaire de spécifier clé comme décrit ci-dessus.
Spécifiez l'ordre inverse avec reverse. Peut être utilisé avec sort () ou sorted ().
Recommended Posts