War in Diskussion https://togetter.com/li/776049
Verwenden Sie es entsprechend dem Eingabeformat richtig?
https://www.hamayanhamayan.com/entry/2018/09/17/163004
Jedes Mal, wenn Sie einen Knoten verbinden, werden die Auswahlmöglichkeiten erweitert, und Sie möchten immer den kleinsten auswählen. → Verwenden Sie eine Prioritätswarteschlange (Heapq).
Wenn ein Taple an heapq übergeben wird, wird der Mindestwert durch das erste Element bestimmt.
O(ElogV)。 Ist es mit dem Fibonacci-Haufen schneller?
https://algo-logic.info/prim-mst/
Prim-Methode
import heapq
def main():
n = int(input())
next = [] #Adjazenzmanagementliste
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
#Verbinden Sie sich mit diesem Knoten
visited[v] = 1
connection += 1
ans += cost
#Enqueue, wohin Sie vom neu verbundenen Knoten gehen können
for i in next[v]:
heapq.heappush(q, i)
#Beenden Sie das Programm, wenn alle Knoten verbunden sind
if connection == n:
break
print(ans)
return
1 → Sortieren nach den Kosten der Seite. Verwenden Sie die Technik des Sortierens nach dem ersten Element, wenn jedes Element der Liste tabellarisch aufgeführt und sortiert ist. 2 → "Straße schließen" = "Machen Sie eine Seite, auf der die beiden Punkte bereits verbunden sind", überprüfen Sie dies mit dem Union Find-Baum.
O(ElogV)。
https://algo-logic.info/kruskal-mst/
Clascal-Methode
def main():
V, E = map(int, input().split())
uf = UnionFind(V)
#Prozess von 1
edges = []
for _ in range(E):
s, t, w = map(int, input().split())
edges.append((w, s, t))
edges.sort()
#Prozess 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
Nachtrag (6/1)
ARC076 D - Built? Erstens: Erwägen Sie, E im Voraus zu reduzieren, wenn es sehr groß ist. → Dieses Mal haben wir verwendet, dass Städte, die sowohl auf der x- als auch auf der y-Koordinate nicht nebeneinander liegen, nicht ausgewählt werden. Zweitens: Wenn sowohl die x-Achse als auch die y-Achse benachbarten Städten entsprechen, werden sie zweimal gezählt, aber das ist mir egal.
def main():
N = int(input())
nodes = []
for i in range(N):
x, y = map(int, input().split())
nodes.append((x, y, i)) #Wenn die Koordinaten eindeutig sind, können Sie sie als Taples in Union Find einfügen. Da es jedoch Fälle gibt, in denen Städte mit denselben Koordinaten vorhanden sind, nummerieren Sie sie.
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
Gibt den Schlüssel zum Sortieren der Liste der Taples an.
#Normalerweise sortiert nach dem ersten Element des Taple.
sortedByFirstKey = sorted(listOfTuple)
#Geben Sie einen Lambda-Ausdruck für Key an, damit er nach dem zweiten Element des Taples sortiert wird.
sortedBySecondKey = sorted(listOfTuple, key=lambda i: i[1])
# reverse
sortedBySecondKey = sorted(listOfTuple, key=lambda i: i[1], reverse=True)
Insbesondere beim Versuch, die Liste der Wörterbücher zu sortieren, tritt ein Fehler auf. Daher muss der oben beschriebene Schlüssel angegeben werden.
Geben Sie die umgekehrte Reihenfolge mit "umgekehrt" an. Kann entweder mit sort () oder sorted () verwendet werden.
Recommended Posts