[Pour les professionnels de la compétition] Résumé de l'arborescence de surface minimale

Méthode pour trouver l'arborescence de la superficie totale minimale

Utiliser correctement

É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

Méthode Prim

  1. Commencez à partir de n'importe quel point de départ.
  2. Sélectionnez et connectez les nœuds mobiles au moindre coût.
  3. Répétez 2 et lorsque tous les nœuds sont connectés, cela devient l'arborescence de la zone entière minimale.

Que devrais-je faire

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.

Ce qui est bon

O(ElogV)。 Est-ce plus rapide avec le tas de Fibonacci?

image

https://algo-logic.info/prim-mst/

Exemple d'utilisation

AOJ ALDS1_12_A

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

Méthode Clascal

  1. Sélectionnez tous les côtés par ordre croissant de poids.
  2. Supprimez tout ce qui crée un chemin fermé dans le processus. Faites cela pour tous les côtés.
  3. Seul le côté finalement sélectionné devient l'arborescence de la superficie totale minimale.

Que devrais-je faire

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.

Ce qui est bon

O(ElogV)。

image

https://algo-logic.info/kruskal-mst/

Exemple d'utilisation

AOJ GRL_2_A

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)

En pensant

Exemple d'application

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 ().


référence

Recommended Posts

[Pour les professionnels de la compétition] Résumé de l'arborescence de surface minimale
[Pour les professionnels de la concurrence] Union Find tree summary
Résumé de la recherche Bisection pour les professionnels de la concurrence
[Pour les professionnels de la compétition] Résumé de la compression de la longueur de tirage
[Pour les professionnels de la concurrence] Résumé du doublement
[Pour les professionnels de la concurrence] Résumé des facteurs premiers, des réductions et des facteurs premiers
Arborescence de surface totale minimale en C #
[Pour les professionnels de la concurrence] Résumé de la file d'attente prioritaire (heapq)
Résumé de l'apprentissage RAPIDS