fork download
copy 
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. class Main
  5. {   
  6.    static Vector<Triple> vect;
  7.    static UF uf;
  8.    static int min;
  9.  
  10.    public static void main(String[] args) throws IOException
  11.    {
  12.       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  13.  
  14.       BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
  15.  
  16.       StringBuffer str = new StringBuffer();
  17.  
  18.       String line = br.readLine();
  19.  
  20.  
  21.       StringTokenizer sTok = new StringTokenizer(line);
  22.  
  23.       int n = Integer.parseInt(sTok.nextToken());
  24.  
  25.       int m = Integer.parseInt(sTok.nextToken());
  26.  
  27.       int l = 0;
  28.  
  29.       while(n + m != 0)
  30.       {
  31.          l++;
  32.  
  33.          vect = new Vector<Triple>();
  34.  
  35.          uf = new UF(n);
  36.  
  37.          min = 0;
  38.  
  39.          for(int i = 0; i < m; i++)
  40.          {
  41.             line = br.readLine();
  42.  
  43.             sTok = new StringTokenizer(line);
  44.  
  45.             int a = Integer.parseInt(sTok.nextToken()) - 1;
  46.  
  47.             int b = Integer.parseInt(sTok.nextToken()) - 1;
  48.  
  49.             int c = Integer.parseInt(sTok.nextToken());
  50.  
  51.             vect.add(new Triple(c,a,b));
  52.          }
  53.  
  54.          line = br.readLine();
  55.  
  56.          sTok = new StringTokenizer(line);
  57.  
  58.          int start = Integer.parseInt(sTok.nextToken()) - 1;
  59.  
  60.          int finish = Integer.parseInt(sTok.nextToken()) - 1;
  61.  
  62.          double tou = Double.parseDouble(sTok.nextToken());
  63.  
  64.  
  65.          Collections.sort(vect);
  66.  
  67.  
  68.          for(int i = 0; i < vect.size(); i++)
  69.          {
  70.             if(uf.sameSet(start, finish))
  71.                break;
  72.  
  73.             Triple t = vect.get(i);
  74.  
  75.             int w = t.w;
  76.  
  77.             int v1 = t.v1;
  78.  
  79.             int v2 = t.v2;
  80.  
  81.             if(!uf.sameSet(v1, v2))
  82.             {
  83.                min = w;
  84.                uf.union(v1, v2);
  85.             }
  86.          }
  87.  
  88.          int result = 0;
  89.  
  90.          if(min > 0)
  91.          {
  92.             min = min - 1;
  93.             result = (int) Math.ceil(tou / min);
  94.          }
  95.  
  96.  
  97.          str.append("Scenario #" + l + "\n");
  98.          str.append("Minimum Number of Trips = " + result + "\n\n");
  99.  
  100.  
  101.          line = br.readLine();
  102.  
  103.          sTok = new StringTokenizer(line);
  104.  
  105.          n = Integer.parseInt(sTok.nextToken());
  106.  
  107.          m = Integer.parseInt(sTok.nextToken());
  108.       }
  109.  
  110.  
  111.       out.write(str.toString());
  112.  
  113.       out.flush();
  114.  
  115.    }
  116. }
  117.  
  118. class UF
  119. {
  120.    int[] array;
  121.    int[] sizes;
  122.    int count;
  123.  
  124.    UF(int n)
  125.    {
  126.       array = new int[n];
  127.       sizes = new int[n];
  128.       count = n;
  129.  
  130.       for(int i = 0; i < n; i++)
  131.       {
  132.          array[i] = i;
  133.          sizes[i] = 1;
  134.       }
  135.    }
  136.  
  137.    int size()
  138.    {
  139.       return count;
  140.    }
  141.  
  142.    int findSet(int i)
  143.    {
  144.       if(array[i] == i)
  145.          return i;
  146.       else
  147.          return findSet(array[i]);
  148.    }
  149.  
  150.    boolean sameSet(int i, int j)
  151.    {
  152.       return findSet(i) == findSet(j);
  153.    }
  154.  
  155.    void union(int i, int j)
  156.    {
  157.       int a = findSet(i);
  158.       int b = findSet(j);
  159.  
  160.       if(a != b)
  161.       {
  162.          if(sizes[a] > sizes[b])
  163.          {
  164.             array[b] = a;
  165.             sizes[a] += sizes[b];
  166.          }
  167.          else
  168.          {
  169.             array[a] = b;
  170.             sizes[b] += sizes[a];
  171.          }
  172.  
  173.          count--;
  174.       }
  175.    }
  176. }
  177.  
  178. class Triple implements Comparable<Triple>
  179. {
  180.    int w;
  181.    int v1;
  182.    int v2;
  183.  
  184.    Triple(int a, int b, int c)
  185.    {
  186.       w = a;
  187.       v1 = b;
  188.       v2 = c;
  189.    }
  190.  
  191.    @Override
  192.    public int compareTo(Triple that) {
  193.       if(this.w > that.w)
  194.          return -1;
  195.       else if(this.w < that.w)
  196.          return 1;
  197.       else
  198.          return 0;
  199.    }
  200. }
  201.  
Runtime error #stdin #stdout 0.09s 380224KB
comments (?)
stdin
copy 
7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 1 99

7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 1 99
0 0
stdout
copy 
Standard output is empty
https://ideone.com/RKyqfb
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!