Runda 4: Wielka Teoria Wszystkiego
24.06.2009
Matematyka jest jak wielkie, rozłożyste drzewo: ma korzenie, pień, grube gałęzie, konary, wreszcie cieńkie gałęzie i niepozorne listeczki. Listeczków tych jest wiele, tak wiele, że nikt nie może się w tym do końca połapać. Dlatego matematycy poświęcają swe życia, aby opiekować się tym wielkim drzewem. Każdy siedzi na swojej gałęzi i obcina listeczki, albo przynajmniej stara sie kontrolować ich ilość. Jednak Ty jesteś matematykiem innowacyjnym - matematykiem XXI wieku. Postanowiłeś opracować Wielką Teorię Wszystkiego, która zastąpi dotychczasowe teorie, będzie prosta, piękna, uniwersalna i obejmie całą matematykę. Pierwszym krokiem twego planu jest dokonanie Wielkiej Unifikacji - mianowicie chcesz udowodnić, że wszystkie teorie z pewnego zbioru są równoważne. Oczywiście nie musisz udowadniać równoważności każdej pary teorii, jako doskonały matematyk dobrze wiesz, że jeżeil A jest równoważne B, a B jest równoważne C, to A jest równoważne C. Oszacowałeś ilość pracy wymaganej, aby udowodnić równoważność niektórych teorii. Ponieważ jesteś leniwym matematykiem, zastanawiasz się, jaka jest minimalna ilość pracy wymagana, aby udowodnić równoważność wszystkich teorii w zbiorze. WejścieW pierwszej linii wejścia dane są dwie liczby n, m (1 ≤ n ≤ 7 000, 1 ≤ m ≤ 1 000 000), oznaczające odpowiednio ilość teorii w zbiorze oraz ilość par, dla których oszacowałeś koszt udowodnienia równoważności. Następnie danych jest m lini, z których każda zawiera trzy liczby a, b, c (1 ≤ a, b ≤ n, 1 ≤ c ≤ 1 000) oznaczające, że koszt udowodnienia równoważności teorii a oraz b wynosi c. WyjścieNa wyjściu należy wypisać jedną liczbę całkowitą - minimalny koszt udowodnienia równoważności wszystkich teorii w zbiorze. PrzykładDla danych wejściowych 6 12 poprawną odpowiedzią jest 22 kod: LAZYMATH, limity: 6 s, 32 MB |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com