Editing 1974 - TrumpLandia


După o confruntare eroică, Trump a fost ales democratic președintele unei republici prospere, ''TrumpLandia''. Natural, prima sa prioritate e să construiască o rețea de buncăre, pentru a veni în întâmpinarea unui atac al vecinilor imperaliști.

<code>N</code> buncăre au fost deja construite. Trump trebuie să aleagă între <code>M</code> posibile rute bidirecționale pentru a le conecta. Un plan de conectare este alcătuit dintr-un subset minim de astfel de legături, astfel încât din fiecare locație să se poată ajunge în orice altă locație. Costul unui plan este dat de suma distanțelor legăturilor.

Deoarece rutele sunt vulnerabile la bombardamente aeriene, Trump vă cere să estimați un plan de cost minim. În plus, Trump vă cere să calculați <code>Q</code> soluții de rezervă, pentru situația în care una dintre cele <code>M</code> legături este sigur inclusă în plan.

= Date de intrare =
Datele de intrare vor fi citite din fișierul <code>trumplandia.in</code>. Pe prima linie se află trei numere separate prin spațiu: <code>N</code> (numărul de buncăre), <code>M</code> (numărul de rute posibile), <code>Q</code> (numărul de soluții de rezervă).

Pe următoarele <code>M</code> linii se află triplete de forma (<code>nod1</code>, <code>nod2</code>, <code>dist12</code>) ce descriu o posibilă legătură între nodurile <code>nod1</code> și <code>nod2</code> cu distanța <code>dist12</code>.

Pe următoarele <code>Q</code> linii se află câte un număr <code>Qi</code>, reprezentând indexul unei muchii care trebuie inclusă într-un plan de rezervă. (valorile se pot repeta)

= Date de ieșire =
Datele de ieșire vor fi afișate în fișierul <code>trumplandia.out</code>.

Pe prima linie se va afla un număr reprezentând costul celui mai bun plan, pentru situația în care pot fi folosite oricare dintre cele <code>M</code> rute.

Pe următoarele <code>Q</code> linii se află un număr <code>Ci</code> reprezentând costul minim al unui plan care conține muchia <code>Qi</code>.

= Restricții și precizări =

* <code>1 ≤ N ≤ 200.000</code> (pentru <code>30%</code> din teste <code>N ≤ 1000</code>)
* <code>N-1 ≤ M ≤ 200.000</code> (pentru <code>30%</code> din teste <code>M ≤ 1000</code>)
* <code>1 ≤ Q ≤ 300.000</code> (pentru <code>30%</code> din teste <code>Q ≤ 1000</code>)
* distanța asociată unei rute este o valoare întreagă din intervalul <code>[1, 1.000.000.000]</code>.

ATENȚIE!!! Între oricare două buncăre pot exista MAI MULTE rute de distanțe diferite sau nu. Exemplu: <code>(1 2 4)</code> și <code>(1 2 6)</code> sunt două muchii între buncărele <code>1</code> și <code>2</code> de distanțe <code>4</code>, respectiv <code>6</code>.

= Exemplu: =
<code>trumplandia.in</code>
 6 8 8
 1 2 4
 4 1 6
 3 1 2
 2 3 3
 5 2 4
 3 4 3
 4 5 5
 5 6 1
 1
 2
 3
 4
 5
 6
 7
 8
<code>trumplandia.out</code>
 13
 14
 16
 13
 13
 13
 13
 14
 13

== Rezolvare ==
<syntaxhighlight lang="python3">

with open("trumplandia.in", "r") as fin:
    N, M, Q = map(int, fin.readline().split())
    edges = [tuple(map(int, fin.readline().split())) for _ in range(M)]
    reserve_edges = [int(fin.readline()) for _ in range(Q)]




def find(parent, node):
    if parent[node] == node:
        return node
    parent[node] = find(parent, parent[node])
    return parent[node]


def union(parent, rank, x, y):
    x = find(parent, x)
    y = find(parent, y)
    if x == y:
        return False
    if rank[x] < rank[y]:
        parent[x] = y
    elif rank[x] > rank[y]:
        parent[y] = x
    else:
        parent[y] = x
        rank[x] += 1
    return True


def kruskal(edges, N):
    edges.sort(key=lambda x: x[2])  

    parent = list(range(N + 1))  
    rank = [0] * (N + 1) 
    min_cost = 0  

    mst_edges = []  

    for edge in edges:
        u, v, cost = edge
        if find(parent, u) != find(parent, v):
            union(parent, rank, u, v)
            min_cost += cost
            mst_edges.append(edge)

    return min_cost, mst_edges


min_cost, mst_edges = kruskal(edges, N)


adj_list = {i: [] for i in range(1, N + 1)}
for edge in mst_edges:
    u, v, cost = edge
    adj_list[u].append((v, cost))
    adj_list[v].append((u, cost))


with open("trumplandia.out", "w") as fout:
    fout.write(str(min_cost) + '\n')
    for reserve_edge in reserve_edges:
        reserve_cost = min_cost  

        if reserve_edge not in [edge[:2] for edge in mst_edges]:
            u, v, cost = edges[reserve_edge - 1]
            for edge in mst_edges:
                if edge[0] == u or edge[1] == u or edge[0] == v or edge[1] == v:
                    reserve_cost += cost - edge[2]
                    break

        fout.write(str(reserve_cost) + '\n')

</syntaxhighlight>