Programozó versenyek

DEIK Regionális Programozó Csapatverseny, egyetemi/főiskolai kategória, 2015. november 29.

2015. november 29. 10:40 – 2015. november 29. 15:40

Sötét utcák

Nehéz időket élünk manapság gazdaságilag, még Bájtföldön is. A működési költségek csökkentése érdekében Bájtföld kormánya úgy döntött, hogy optimalizálja az utcai világítást. Ezidáig minden utca egész éjjel ki volt világítva, amely naponta és méterenként 1 bájtföldi dollárba került. Hogy pénzt takarítsanak meg, úgy döntöttek, hogy ezután nem világítanak ki minden utcát, hanem lekapcsolják a világítást bizonyos utcákban. Hogy Bájtföld lakói továbbra is biztonságban érezzék magukat, úgy akarják optimalizálni a világítást, hogy miután elsötétítenek éjszakára néhány utcát, még mindig maradjon legalább egy kivilágított útvonal Bájtföld minden kereszteződéséből minden másik kereszteződésébe.

Mekkora az a maximális összeg, amelyet Bájtföld kormánya naponta meg tud takarítani anélkül, hogy a lakói veszélyben éreznék magukat?

A bemenet specifikációja

A bemenet számos tesztesetet tartalmaz. Minden teszteset két számmal, m-mel és n-nel kezdődik, amelyek rendre Bájtföld kereszteződéseinek és útjainak a számát jelölik. A bemenetet az m = n = 0 eset zárja. Minden más esetben 1 ≤ m ≤ 200 000 és m – 1 ≤ n ≤ 200 000. Ezután n darab x, y, z számhármas következik, amelyek azt jelentik, hogy x és y között létezik egy z méter hosszú kétirányú utca (0 ≤ xy < m és x ≠ y). Minden teszteset összefüggő gráfot ír le. Az utcák összhosszúsága minden tesztesetben kisebb, mint 231.

A kimenet specifikációja

Minden tesztesetre egy sort kell a kimenetre írni, amely azt a maximális összeget tartalmazza, amennyit a kormány egy nap alatt meg tud takarítani.

Példa bemenet

  1. 7 11
  2. 0 1 7
  3. 0 3 5
  4. 1 2 8
  5. 1 3 9
  6. 1 4 7
  7. 2 4 5
  8. 3 4 15
  9. 3 5 6
  10. 4 5 8
  11. 4 6 9
  12. 5 6 11
  13. 0 0
letöltés szöveges állományként

A példa bemenethez tartozó kimenet

  1. 51
letöltés szöveges állományként
Debreceni Egyetem, Informatikai Kar, v. 2019.03.01.