30ος ΠΔΠ Καμπ (seniors)
Η γέφυρα της Καζάρμας (kazarma)

Η γέφυρα της Καζάρμας (διαστάσεις 22 × 5,60 × 4 μ.) κατασκευάσθηκε κατά την μυκηναϊκή εποχή, γύρω στο 1300 π.Χ. και βρίσκεται κατά μήκος ενός καλοκατασκευασμένου μυκηναϊκού δρόμου που συνέδεε τις Μυκήνες και την Τίρυνθα με την Επίδαυρο. Η μυκηναϊκή γέφυρα της Καζάρμας χρησιμοποιείται και σήμερα από τους κατοίκους της περιοχής… [http://odysseus.culture.gr/]

Η ιστορία της συγκεκριμένης γέφυρας έχει ως εξής. Ένα σύνολο 10 πόλεων (εκ των οποίων προφανώς οι Μυκήνες, η Τίρυνθα και η Επίδαυρος) διατηρούσαν μία συμμαχία. Για το λόγο αυτό ήθελαν να μπορούν να βρίσκονται πάντα σε επικοινωνία και χτίσανε δρόμους (και γέφυρες) που να τις συνδέουν. Δυστυχώς ο προϋπολογισμός ήταν περιορισμένος κι έτσι μεταξύ κάθε ζεύγους πόλεων υπήρχε αρχικά ακριβώς ένας τρόπος μετάβασης. Μετά από πολύ κόπο, συγκεντρώθηκαν αρκετά χρήματα ώστε να χτιστεί άλλος ένας δρόμος. Αυτό σημαίνει ότι δεν θα υπήρχε πια μοναδικός τρόπος μετάβασης μεταξύ κάθε ζεύγους πόλεων. Όμως κάθε πολίτης, για να μη χρειάζεται να θυμάται πολλούς δρόμους, ξέρουμε ότι διαλέγει ένα ελάχιστο σύνολο δρόμων το οποίο του επιτρέπει να κινείται μεταξύ όλων των πόλεων. Προφανώς θέλει το άθροισμα των μηκών αυτών των δρόμων να είναι ελάχιστο ώστε να γίνονται γρήγορα οι μετακινήσεις του.

Θέλοντας να έχουν πολλά τέτοια σύνολα δρόμων που να μπορούν να επιλέξουν και να πληρούν τις παραπάνω απαιτήσεις, οι πολίτες της συμμαχίας αποφάσισαν το χτίσιμο της γέφυρας της Καζάρμας.

Σήμερα θέλουμε να ελέγξουμε αν πράγματι το σημείο αυτό ήταν το βέλτιστο. Σκοπεύουμε λοιπόν να φτιάξουμε ένα πρόγραμμα που, δεδομένης μίας συμμαχίας με \(N\) πόλεις, βρίσκει το βέλτιστο δρόμο που μπορούμε να προσθέσουμε ώστε να μεγιστοποιηθεί το πλήθος των επιλογών.

Δεδομένα εισόδου (kazarma.in)

Η πρώτη γραμμή της εισόδου θα περιέχει ένα φυσικό αριθμό \(N\): το πλήθος \(N\) των πόλεων της συμμαχίας. Οι επόμενες \(N-1\) γραμμές περιγράφουν από ένα δρόμο η κάθε μία. Πιο συγκεκριμένα, η \(i\)-οστή από αυτές περιέχει τρεις φυσικούς \(u_i\), \(v_i\), \(s_i\) όπου \(1 \leq u_i, v_i \leq N\) οι αριθμοί των πόλεων που συνδέει ο δρόμος, και \(1 \leq s_i \leq N\) το μήκος του.

Δεδομένα εξόδου (kazarma.out)

Η έξοδος πρέπει να περιέχει μία γραμμή με ακριβώς ένα φυσικό αριθμό: το πλήθος επιλογών που προσφέρει ο βέλτιστος δρόμος.

Παράδειγμα αρχείων εισόδου - εξόδου

kazarma.in	kazarma.out
4 1 2 1 2 3 1 2 4 2	3

Εξήγηση: Ο βέλτιστος δρόμος είναι αυτός που συνδέει τις πόλεις \(1\)-\(3\) με μήκος \(1\). Τότε κάθε πολίτης μπορεί να επιλέξει το σύνολο δρόμων του από τις εξής \(3\) επιλογές, όλες με συνολικό μήκος \(4\):

\(\{1\text{-}2, 1\text{-}3, 2\text{-}4\}\) ή \(\{1\text{-}3, 2\text{-}3, 2\text{-}4\}\) ή \(\{1\text{-}2, 2\text{-}3, 2\text{-}4\}\)

Προσοχή: αν βάζαμε το δρόμο \(1\text{-}4\) με μήκος \(1\), μπορεί να παίρναμε συνολικό μήκος \(3\) αλλά θα υπήρχε μόνο μία επιλογή κι έτσι δε τον προτιμούμε.

Περιορισμοί

Όριο χρόνου εκτέλεσης: \(1\) sec.
Όριο μνήμης: \(64\) MB.

Υποπροβλήματα