CSES - Tiedonvälitys

Annettuna on tietoverkko, jossa on n tietokonetta ja niiden välisiä yhteyksiä. Jokaisen yhteyden kautta voi lähettää tietoa koneesta toiseen tietyn määrän bittejä sekunnissa.

Tehtäväsi on tutkia, mikä on suurin mahdollinen tiedon määrä, joka voidaan välittää annetusta koneesta toiseen sekunnissa.

Voit olettaa, että tietokoneita on enintään 50 ja luokan metodeita kutsutaan enintään 100 kertaa. Jokaisen yhteyden siirtomäärä on kokonaisluku välillä 1 \dots 1000.

Toteuta tiedostoon download.py luokka Download, jossa on seuraavat metodit:

  • konstruktori, jolle annetaan tietokoneiden määrä
  • add_link lisää koneesta a koneeseen b yhteyden, joka siirtää x bittiä sekunnissa
  • calculate laskee suurimman mahdollisen siirtomäärän koneesta a koneeseen b
class Download:
    def __init__(self,n):
        # TODO

    def add_link(self,a,b,x):
        # TODO

    def calculate(self,a,b):
        # TODO

if __name__ == "__main__":
    d = Download(4)
    print(d.calculate(1,4)) # 0
    d.add_link(1,2,5)
    d.add_link(2,4,6)
    d.add_link(1,4,2)
    print(d.calculate(1,4)) # 7
    d.add_link(1,3,4)
    d.add_link(3,2,2)
    print(d.calculate(1,4)) # 8