4244 - urgenta

Autorităţile dintr-o zonă de munte intenţionează să stabilească un plan de urgenţă, pentru a reacţiona mai eficient la frecventele calamităţi naturale din zonă. În acest scop au identificat N puncte de interes strategic şi le-au numerotat distinct de la 1 la N. Punctele de interes strategic sunt conectate prin M căi de acces având priorităţi în funcţie de importanţă. Între oricare două puncte de interes strategic există cel mult o cale de acces ce poate fi parcursă în ambele sensuri şi cel puţin un drum (format din una sau mai multe căi de acces) ce le conectează.

În cazul unei calamităţi unele căi de acces pot fi temporar întrerupte şi astfel între anumite puncte de interes nu mai există legătură. Ca urmare pot rezulta mai multe grupuri de puncte în aşa fel încât între oricare două puncte din acelaşi grup să existe măcar un drum şi între oricare două puncte din grupuri diferite să nu existe drum.

Cerința

Autorităţile estimează gravitatea unei calamităţi ca fiind suma priorităţilor căilor de acces distruse de aceasta şi doresc să determine un scenariu de gravitate maximă, în care punctele de interes strategic să fie împărţite într-un număr de K grupuri.

Date de intrare

Fișierul de intrare urgenta.in are următorul format:

N M K

i1 j1 p1 – între punctele i1 şi j1 există o cale de acces de prioritate p1.

i2 j2 p2 – între punctele i2 şi j2 există o cale de acces de prioritate p2.

…

iM jM pM – între punctele iM şi jM există o cale de acces de prioritate pM.

Date de ieșire

Fișierul de ieșire urgenta.out va avea următorul format:

gravmax – gravitatea maximă

C – numărul de căi de acces întrerupte de calamitate

k1 h1 – între punctele k1 şi h1 a fost întreruptă calea de acces

k2 h2 – între punctele k2 şi h2 a fost întreruptă calea de acces

…

kC hC – între punctele kC şi hC a fost întreruptă calea de acces

Restricții și precizări

• 0 < N < 256
• N - 2 < M < 32385
• 0 < K < N + 1
• Priorităţile căilor de acces sunt întregi strict pozitivi mai mici decât 256.
• Un grup de puncte poate conţine între 1 şi N puncte inclusiv.
• Dacă există mai multe soluţii, programul va determina una singură.

Exemplu:

urgenta.in

7 11 4
1 2 1
1 3 2
1 7 3
2 4 3
3 4 2
3 5 1
3 6 1
3 7 5
4 5 5
5 6 4
6 7 3

urgenta.out

27
8
1 3
1 7
2 4
3 4
3 7
4 5
5 6
6 7

Rezolvare

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            elif self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1


def main():
    nMAX = 255
    fin = open("urgenta.in", "r")
    fout = open("urgenta.out", "w")

    n, m, k = map(int, fin.readline().split())
    edges = []
    edges_fol = [False] * (m + 1)
    tat = [0] * (nMAX + 1)
    niv = [0] * (nMAX + 1)
    grupe, edgfol = n, 0
    costall, costfol = 0, 0

    for _ in range(m):
        a, b, c = map(int, fin.readline().split())
        costall += c
        edges.append((c, a, b))

    edges.sort()

    def rad(nod):
        if tat[nod]:
            return rad(tat[nod])
        return nod

    def changeDads(nod, newdad):
        if tat[nod]:
            changeDads(tat[nod], newdad)
        tat[nod] = newdad

    for i in range(m):
        if grupe == k:
            break
        c, a, b = edges[i]
        rada = rad(a)
        radb = rad(b)

        if rada != radb:
            if niv[rada] < niv[radb]:
                changeDads(a, radb)
            elif niv[rada] > niv[radb]:
                changeDads(b, rada)
            else:
                niv[rada] += 1
                changeDads(b, rada)
            
            edges_fol[i] = True
            edgfol += 1
            costfol += c
            grupe -= 1

    fout.write(str(costall - costfol) + '\n')
    fout.write(str(m - edgfol) + '\n')
    for i in range(m):
        if not edges_fol[i]:
            fout.write(str(edges[i][1]) + ' ' + str(edges[i][2]) + '\n')

    fin.close()
    fout.close()


if __name__ == "__main__":
    main()