CSES - Samat painot

Tehtäväsi on tutkia, onko annetun verkon jokaisella virittävällä puulla sama paino.

Voit olettaa, että solmuja on enintään 50 ja luokan metodeita kutsutaan enintään 100 kertaa. Jokaisen kaaren paino on kokonaisluku välillä 1 \dots 1000.

Python

Toteuta tiedostoon sameweight.py luokka SameWeight, jossa on seuraavat metodit:

  • konstruktori, jolle annetaan solmujen määrä
  • add_edge lisää solmujen a ja b välille kaaren, jonka paino on x
  • check ilmoittaa, onko verkon kaikilla virittävillä puilla sama paino (jos verkko ei ole yhtenäinen, haluttu vastaus on True)
class SameWeight:
    def __init__(self,n):
        # TODO

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

    def check(self):
        # TODO

if __name__ == "__main__":
    s = SameWeight(4)
    s.add_edge(1,2,2)
    s.add_edge(1,3,3)
    print(s.check()) # True
    s.add_edge(1,4,3)
    print(s.check()) # True
    s.add_edge(3,4,3)
    print(s.check()) # True
    s.add_edge(2,4,1)
    print(s.check()) # False

Java

Toteuta tiedostoon SameWeight.java luokka SameWeight, jossa on seuraavat metodit:

  • konstruktori, jolle annetaan solmujen määrä
  • addEdge lisää solmujen a ja b välille kaaren, jonka paino on x
  • check ilmoittaa, onko verkon kaikilla virittävillä puilla sama paino (jos verkko ei ole yhtenäinen, haluttu vastaus on true)
public class SameWeight {
    public SameWeight(int n) {
        // TODO
    }

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

    public boolean check() {
        // TODO
    }

    public static void main(String[] args) {
        SameWeight s = new SameWeight(4);
        s.addEdge(1,2,2);
        s.addEdge(1,3,3);
        System.out.println(s.check()); // true
        s.addEdge(1,4,3);
        System.out.println(s.check()); // true
        s.addEdge(3,4,3);
        System.out.println(s.check()); // true
        s.addEdge(2,4,1);
        System.out.println(s.check()); // false
    }
}