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$.

Python

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
Java

Toteuta tiedostoon Download.java luokka Download, jossa on seuraavat metodit:
  • konstruktori, jolle annetaan tietokoneiden määrä
  • addLink lisää koneesta $a$ koneeseen $b$ yhteyden, joka siirtää $x$ bittiä sekunnissa
  • calculate laskee suurimman mahdollisen siirtomäärän koneesta $a$ koneeseen $b$
public class Download {
    public Download(int n) {
        // TODO
    }

    public void addLink(int a, int b, int x) {
        // TODO
    }

    public int calculate(int a, int b) {
        // TODO
    }

    public static void main(String[] args) {
        Download d = new Download(4);
        System.out.println(d.calculate(1,4)); // 0
        d.addLink(1,2,5);
        d.addLink(2,4,6);
        d.addLink(1,4,2);
        System.out.println(d.calculate(1,4)); // 7
        d.addLink(1,3,4);
        d.addLink(3,2,2);
        System.out.println(d.calculate(1,4)); // 8
    }
}