Source code for submission s690

Fr.java

  1.  
  2. import java.util.ArrayList;
  3. import java.util.Scanner;
  4.  
  5. /**
  6.  *
  7.  * @author cteam023
  8.  */
  9. public class Fr {
  10.  
  11.     private Uzel[] uzly;
  12.     private int centralniUzel;
  13.  
  14.  
  15.  
  16.  
  17.     public Fr(int pocetUzlu, int centralniUzel){
  18.         uzly = new Uzel[pocetUzlu];        
  19.         for (int i = 0; i < pocetUzlu; i++){
  20.             uzly[i] = new Uzel();
  21.         }
  22.         this.centralniUzel = centralniUzel;
  23.     }
  24.  
  25.     public void pridejSpojeni(int uzel1, int uzel2, int sila){
  26.         Spojeni spoj = new Spojeni(uzly[uzel1], uzly[uzel2], sila);
  27.         uzly[uzel1].pridejSpojeni(spoj);
  28.         uzly[uzel2].pridejSpojeni(spoj);
  29.     }
  30.  
  31.     public void vyres(){
  32.         int vysl = uzly[centralniUzel].getNejmensi();
  33.         System.out.println(vysl);
  34.     }
  35.  
  36.  
  37.     public static void main(String[] args) {
  38.         Scanner sc = new Scanner(System.in);
  39.         int pocetUzlu;
  40.         int centralni;
  41.         while (sc.hasNextInt()){
  42.             pocetUzlu = sc.nextInt();
  43.             centralni = sc.nextInt();
  44.             Fr pripad = new Fr(pocetUzlu, centralni - 1);            
  45.             for (int i = 0; i < pocetUzlu -1; i++){
  46.                 pripad.pridejSpojeni(sc.nextInt() - 1, sc.nextInt() - 1, sc.nextInt());
  47.             }
  48.             pripad.vyres();
  49.         }
  50.  
  51.     }
  52.  
  53.     private static class Uzel{        
  54.         private int expand;
  55.  
  56.         private ArrayList<Spojeni> spojeni;
  57.  
  58.  
  59.         public Uzel(){
  60.             expand = Integer.MAX_VALUE;
  61.             spojeni = new ArrayList<Spojeni>();
  62.         }
  63.  
  64.         public void pridejSpojeni(Spojeni spoj){            
  65.             spojeni.add(spoj);
  66.         }
  67.  
  68.         public int getNejmensi(){
  69.             this.expand = 0;
  70.             for (Spojeni i : spojeni){
  71.                 i.getDruhy(this).expanduj(i);
  72.                 this.expand += i.getDruhy(this).expand;
  73.             }
  74.             return this.expand;
  75.  
  76.         }
  77.  
  78.  
  79.         private void expanduj(Spojeni spoj){
  80.             this.expand = spoj.sila;
  81.             int podsoucet = 0;
  82.             for (Spojeni i: spojeni){
  83.                 if (i == spoj){
  84.                     continue;
  85.                 }
  86.                 i.getDruhy(this).expanduj(i);
  87.                 podsoucet += i.getDruhy(this).expand;
  88.             }
  89.             if (podsoucet < this.expand){
  90.                 if (podsoucet == 0){
  91.                     return;
  92.                 }
  93.                 this.expand = podsoucet;
  94.             }
  95.  
  96.         }
  97.  
  98.  
  99.  
  100.     }
  101.  
  102.     private static class Spojeni{
  103.         private Uzel uzel1, uzel2;
  104.         public int sila;
  105.  
  106.         public Spojeni(Uzel uzel1, Uzel uzel2, int sila){
  107.             this.uzel1 = uzel1;
  108.             this.uzel2 = uzel2;
  109.             this.sila = sila;
  110.         }
  111.  
  112.         public Uzel getDruhy(Uzel tento){
  113.             if (tento == uzel1){
  114.                 return uzel2;
  115.             }
  116.             return uzel1;
  117.         }
  118.  
  119.  
  120.  
  121.     }
  122.  
  123. }
  124.