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