Was in discussion https://togetter.com/li/776049
Do you use it properly according to the input format?
https://www.hamayanhamayan.com/entry/2018/09/17/163004
Every time you connect a node, the options expand, and you always want to select the smallest one. → Use priority queue (heapq).
When a tuple is passed to heapq, the minimum value is determined by the first element.
O(ElogV)。 Is it faster with the Fibonacci heap?
https://algo-logic.info/prim-mst/
Prim's algorithm
import heapq
def main():
n = int(input())
next = [] #Adjacency management list
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
#Connect with that node
visited[v] = 1
connection += 1
ans += cost
#Enqueue where you can go from the newly connected node
for i in next[v]:
heapq.heappush(q, i)
#Exit when all nodes are connected
if connection == n:
break
print(ans)
return
1 → Sort based on the cost of the edge. Use the technique of sorting by the first element when each element of the list is made into a tuple and sorted. 2 → "A cycle can be closed" = "Make a side where two points are already connected", so check with the Union Find tree.
O(ElogV)。
https://algo-logic.info/kruskal-mst/
Kruskal method
def main():
V, E = map(int, input().split())
uf = UnionFind(V)
#Process of 1
edges = []
for _ in range(E):
s, t, w = map(int, input().split())
edges.append((w, s, t))
edges.sort()
#Process 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
Postscript (6/1)
ARC076 D - Built? First: Consider reducing E in advance if it is huge. → This time, we used that towns that are not adjacent to each other on the x-coordinate and the y-coordinate cannot be selected. Second: If both the x-axis and y-axis correspond to adjacent towns, they are counted twice, but I don't care.
def main():
N = int(input())
nodes = []
for i in range(N):
x, y = map(int, input().split())
nodes.append((x, y, i)) #If the coordinates are unique, the tuples will be put into Union Find, but since there are cases where there are towns at the same coordinates, number them.
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
Specifies the key for sorting the list of tuples.
#Usually sorted by the first element of the tuple.
sortedByFirstKey = sorted(listOfTuple)
#Specify a lambda expression for Key and sort by the second element of the tuple.
sortedBySecondKey = sorted(listOfTuple, key=lambda i: i[1])
# reverse
sortedBySecondKey = sorted(listOfTuple, key=lambda i: i[1], reverse=True)
Especially when trying to sort the list of dictionaries, an error will occur, so it is necessary to specify key
as described above.
Specify the reverse order with reverse
. Can be used with either sort ()
or sorted ()
.
Recommended Posts