Σας παραθέτω μια προσέγγιση στη λύση του προβλήματος "christmas" του hellenico.gr
Ο αλγόριθμος που χρησιμοποίησα είναι του Kruskal. Η Δομή δεδομένων μου για Disjoint Sets είναι Linked List.
Για το δεύτερο MST κάνω:
Για κάθε edge που ανήκει στο πρώτο MST
την αφαιρώ απο τη λύση και ψαναφτιάχνω το linked list χωρις αυτήν.
τρέχω τον Kruskal απο το σημείο που είχε σταματήσει ο πρώτος αφαιρόντας το κόστος της συγκεκριμένς ακμής
αν το αποτέλεσμα είναι το επόμενο μεγαλύτερο του πρώτου ειναι και το σωστό
(Sorry για τα ορθογραφικά.. δεν είχα το χρόνο για να τα τσεκάρω)
Οποιοδήποτε σχόλιο και διόρθωση είναι καλοδεχούμενα!!!
Κώδικας => http://pastebin.com/4qzCLFu1.
Το Πρόβλημα:
Όσον αφορά στην μορφή της εισόδου, στην πρώτη γραμμή θα δίνεται το πλήθος N των
κορυφών / διασταυρώσεων και το πλήθος M των ακμών / δρόμων. Σε καθεμία από τις
υπόλοιπες M γραμμές θα δίνονται τα χαρακτηριστικά μιας ακμής e: πρώτα δύο
θετικοί ακέραιοι που αντιστοιχούν στα δύο άκρα της ακμής, και έπειτα ένας
θετικός ακέραιος που αντιστοιχεί στο μήκος της d(e).
3<=N<=2000
3<=M<=10^5
1<=d(e)<=10^9
Bonus:
Δύο
επιπλέον παραδείγματα αξιολόγησης με Ν = 50000.
Παράδειγμα εισόδου
(αρχείο "christmas.in")
3 3
2 1 67
3 1 46
3 2
75
Παράδειγμα εξόδου (αρχείο "christmas.out")
113
121
Παράδειγμα εισόδου 2 (αρχείο "christmas.in")
5 9
2 1 29
3 2 52
4 1 20
5 3 45
2 5 42
2 4 19
1 5 5
5 4 26
4 3
76
Παράδειγμα εξόδου 2 (αρχείο "christmas.out")
89
95
Παράδειγμα εισόδου 3 (αρχείο "christmas.in")
6 9
1 2 50
1 3 80
2 3 60
2 4 20
3 5 40
2 5 30
4 5 10
4 6 10
5 6
50
Παράδειγμα εξόδου 3 (αρχείο "christmas.out")
130 140
a2a_linkname="First and Second Minimum Spanning Tree,Kruskal in C";a2a_linkurl="http://www.studentguru.gr/blogs/ikaragkiozoglou/archive/2011/02/24/first-and-second-minimum-spanning-tree-kruskal-in-c.aspx";
