Advertisement
dzocesrce

[APS] Railway Station

Aug 29th, 2023
289
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 16.09 KB | None | 0 0
  1. // Ministerot za transport i vrski ima na raspolaganje odreden budzet koj treba da go iskroisti za da povrzi sto e mozno povekje gradovi preku zeleznicki soobrakjaj so glavnata zeleznicka stanica. Ako cesto patuvate so voz i ste zapoznati so problematikite, upatete go, sekoj sovet e dobredojden:D
  2. import java.util.*;
  3.  
  4. class Graph<E> {
  5.  
  6.     int num_nodes;
  7.     GraphNode<E> adjList[];
  8.  
  9.     @SuppressWarnings("unchecked")
  10.     public Graph(int num_nodes, E[] list) {
  11.         this.num_nodes = num_nodes;
  12.         adjList = (GraphNode<E>[]) new GraphNode[num_nodes];
  13.         for (int i = 0; i < num_nodes; i++)
  14.             adjList[i] = new GraphNode<E>(i, list[i]);
  15.     }
  16.  
  17.     @SuppressWarnings("unchecked")
  18.     public Graph(int num_nodes) {
  19.         this.num_nodes = num_nodes;
  20.         adjList = (GraphNode<E>[]) new GraphNode[num_nodes];
  21.         for (int i = 0; i < num_nodes; i++)
  22.             adjList[i] = new GraphNode<E>(i, null);
  23.     }
  24.  
  25.     int adjacent(int x, int y) {
  26.         // proveruva dali ima vrska od jazelot so
  27.         // indeks x do jazelot so indeks y
  28.         return (adjList[x].containsNeighbor(adjList[y])) ? 1 : 0;
  29.     }
  30.  
  31.     void addEdge(int x, int y, float tezina) {
  32.         // dodava vrska od jazelot so indeks x do jazelot so indeks y so tezina
  33.         // i obratno
  34.         if (adjList[x].containsNeighbor(adjList[y])) {
  35.             adjList[x].updateNeighborWeight(adjList[y], tezina);
  36.             adjList[y].updateNeighborWeight(adjList[x], tezina);
  37.         } else{
  38.             adjList[x].addNeighbor(adjList[y], tezina);
  39.             adjList[y].addNeighbor(adjList[x], tezina);
  40.         }
  41.     }
  42.  
  43.     void deleteEdge(int x, int y) {
  44.         adjList[x].removeNeighbor(adjList[y]);
  45.         adjList[y].removeNeighbor(adjList[x]);
  46.     }
  47.  
  48.     /*************************** KRUSKAL ***********************************************************************/
  49.  
  50.     // Metoda koja generira niza od site rebra vo grafot
  51.     public Edge[] getAllEdges() {
  52.         int totalEdges = 0;
  53.         for (int i = 0; i < this.num_nodes; i++) {
  54.             // za sekoe teme go dodavame brojot na sosedi koi gi ima
  55.             totalEdges += this.adjList[i].getNeighbors().size();
  56.         }
  57.  
  58.         totalEdges /= 2; //bidejki e nenasocen graf, sekoe rebro se javuva kaj dve teminja
  59.  
  60.         Edge[] edges = new Edge[totalEdges];
  61.         int index = 0;
  62.         for (int i = 0; i < this.num_nodes; i++) {
  63.             for (int j = 0; j < this.adjList[i].getNeighbors().size(); j++) {
  64.                 int index1 = this.adjList[i].getIndex();
  65.                 // se zemaat indeksot i tezinata na j-ot sosed na temeto i
  66.                 int index2 = this.adjList[i].getNeighbors().get(j).node
  67.                         .getIndex();
  68.                 float weight = this.adjList[i].getNeighbors().get(j).weight;
  69.                 if(index2>index1) //bidejki grafot e nenasocen, da ne go zemame sekoe rebro dva pati
  70.                     edges[index++] = new Edge(index1, index2, weight);
  71.             }
  72.         }
  73.  
  74.         return edges;
  75.     }
  76.  
  77.     // Metoda koja gi sortira site rebra
  78.     private void sortEdges(Edge[] edges) {
  79.         for (int i = 0; i < edges.length - 1; i++) {
  80.             for (int j = i + 1; j < edges.length; j++) {
  81.                 if (edges[i].getWeight() > edges[j].getWeight()) {
  82.                     Edge tmp = edges[i];
  83.                     edges[i] = edges[j];
  84.                     edges[j] = tmp;
  85.                 }
  86.             }
  87.         }
  88.  
  89.     }
  90.  
  91.     //Metoda koja pravi unija na dve drva
  92.     private void union(int u, int v, int[] vrski){
  93.         int findWhat, replaceWith;
  94.  
  95.         if(u < v){
  96.             findWhat = vrski[v];
  97.             replaceWith = vrski[u];
  98.         }
  99.         else{
  100.             findWhat = vrski[u];
  101.             replaceWith = vrski[v];
  102.         }
  103.  
  104.         //za dvete poddrva stava ist index
  105.         //vo vrski t.e. gi spojuva
  106.         for(int i=0; i<vrski.length; i++){
  107.             if(vrski[i] == findWhat){
  108.                 vrski[i] = replaceWith;
  109.             }
  110.         }
  111.     }
  112.  
  113.     List<Edge> kruskal() {
  114.         /*
  115.          * Pomoshna niza za sledenje na kreiranite drva
  116.          * Ako dve teminja se del od isto poddrvo
  117.          * togash imaat ista vrednost vo nizata
  118.          */
  119.         int vrski[] = new int[this.num_nodes];
  120.  
  121.         // niza koja gi sodrzi site rebra
  122.         Edge[] edges = this.getAllEdges();
  123.         // se sortiraat rebrata spored tezinite vo neopagjacki redosled
  124.         this.sortEdges(edges);
  125.  
  126.         // inicijalizacija na pomosnata niza za evidencija,
  127.         // sekoj jazel si e posebno drvo
  128.         for (int i = 0; i < this.num_nodes; i++)
  129.             vrski[i] = i;
  130.  
  131.         // lista koja kje gi sodrzi MST rebra
  132.         List<Edge> mstEdges = new ArrayList<Edge>();
  133.  
  134.         for(int i=0; i<edges.length; i++){
  135.             //za sekoe rebro vo sortiran redosled
  136.             Edge e = edges[i];
  137.  
  138.             if(vrski[e.getFrom()] != vrski[e.getTo()]){
  139.                 //ako teminjata na ova rebro ne se vo isto poddrvo
  140.                 //ova rebro e MST rebro
  141.                 mstEdges.add(e);
  142.                 //sega dvete teminja treba da se vo isto poddrvo
  143.                 //t.e se pravi merge (unija) t.s. vo nizata vrski
  144.                 //za site elementi od dvete poddrva
  145.                 //go setira istiot (najmal) element od dvete poddrva
  146.                 //vrski = this.union(e.getFrom(), e.getTo(), vrski);
  147.                 this.union(e.getFrom(), e.getTo(), vrski);
  148.             }
  149.  
  150.             //ako sme dodale num_nodes-1 rebra moze da prestaneme
  151.             if(mstEdges.size()==(this.num_nodes-1))
  152.                 break;
  153.         }
  154.  
  155.         return mstEdges;
  156.     }
  157.  
  158.     /*******************************************************************************************************/
  159.     /************************ PRIM **************************************************************************/
  160.  
  161.     //Metoda koja go naogja najmaloto rebro do
  162.     //teme na neposeten sosed
  163.     private Edge getMinimalEdge(boolean[] included){
  164.         int index1 = Integer.MAX_VALUE, index2 = Integer.MAX_VALUE;
  165.         float minweight = Float.MAX_VALUE;
  166.  
  167.         for(int i=0;i<this.num_nodes;i++){
  168.             if(included[i]){
  169.                 //ako e vkluceno temeto i
  170.                 //izmini gi negovite nevkluceni sosedi
  171.                 Iterator<GraphNode<E>.GraphNodeNeighbor<E>> it = adjList[i].getNeighbors().iterator();
  172.                 while(it.hasNext()){
  173.                     GraphNode<E>.GraphNodeNeighbor<E> pom = it.next();
  174.                     //ako sosedot ne e poseten i ima do sega najmala tezina
  175.                     if(!included[pom.node.getIndex()] && pom.weight<minweight){
  176.                         index1 = i;
  177.                         index2 = pom.node.getIndex();
  178.                         minweight = pom.weight;
  179.                     }
  180.                 }
  181.             }
  182.         }
  183.  
  184.         if(minweight<Float.MAX_VALUE){
  185.             Edge ret = new Edge(index1, index2, minweight);
  186.             return ret;
  187.         }
  188.         return null;
  189.     }
  190.  
  191.  
  192.     List<Edge> prim(int start_index) {
  193.         // lista koja kje gi sodrzi MST rebra
  194.         List<Edge> mstEdges = new ArrayList<Edge>();
  195.  
  196.         boolean included[] = new boolean[this.num_nodes];
  197.         for(int i=0;i<this.num_nodes;i++)
  198.             included[i]=false;
  199.  
  200.         included[start_index] = true;
  201.  
  202.         for(int i=0;i<this.num_nodes-1;i++){
  203.             Edge e = this.getMinimalEdge(included);
  204.             if(e==null){
  205.                 System.out.println("Ne mozat da se povrzat site jazli");
  206.                 break;
  207.             }
  208.             included[e.getFrom()] = included[e.getTo()] = true;
  209.             mstEdges.add(e);
  210.         }
  211.  
  212.         return mstEdges;
  213.     }
  214.  
  215.     /*******************************************************************************************************/
  216.     /***************** DIJKSTRA ******************************************************************************/
  217.  
  218.     float[] dijkstra(int from) {
  219.  
  220.         /* Minimalna cena do sekoe od teminjata */
  221.         float distance[] = new float[this.num_nodes];
  222.         /* dali za temeto e najdena konecnata (minimalna) cena */
  223.         boolean finalno[] = new boolean[this.num_nodes];
  224.         for (int i = 0; i < this.num_nodes; i++) {
  225.             distance[i] = -1;
  226.             finalno[i] = false;
  227.         }
  228.  
  229.         finalno[from] = true;
  230.         distance[from] = 0;
  231.  
  232.         /*
  233.          * vo sekoj cekor za edno teme se dobiva konecna minimalna cena
  234.          */
  235.         for (int i = 1; i < this.num_nodes; i++) {
  236.             /* za site sledbenici na from presmetaj ja cenata */
  237.             Iterator<GraphNode<E>.GraphNodeNeighbor<E>> it = adjList[from].getNeighbors().iterator();
  238.             while (it.hasNext()) {
  239.                 GraphNode<E>.GraphNodeNeighbor<E> pom = it.next();
  240.                 /* ako grankata kon sosedot nema konecna cena */
  241.                 if (!finalno[pom.node.getIndex()]) {
  242.                     /* ako ne e presmetana cena za temeto */
  243.                     if (distance[pom.node.getIndex()] <= 0) {
  244.                         distance[pom.node.getIndex()] = distance[from]
  245.                                 + pom.weight;
  246.                     }
  247.                     /* inaku, ako e pronajdena poniska */
  248.                     else if (distance[from] + pom.weight < distance[pom.node
  249.                             .getIndex()]) {
  250.                         distance[pom.node.getIndex()] = distance[from]
  251.                                 + pom.weight;
  252.                     }
  253.                 }
  254.             }
  255.  
  256.             /* najdi teme so min. cena koja ne e konecna */
  257.             boolean minit = false; /* min. ne e inicijaliziran */
  258.             int k = -1;
  259.             float minc = -1;
  260.             /* proveri gi site teminja */
  261.             for (int j = 0; j < this.num_nodes; j++) {
  262.                 if (!finalno[j] && distance[j] != -1) { /*ako cenata ne e  konecna*/
  263.                     if (!minit) { /* ako ne e inicijaliziran minimumot */
  264.                         minc = distance[k = j]; /* proglasi go ova e minimum */
  265.                         minit = true; /* oznaci deka min e inicijaliziran */
  266.                     }
  267.                     /* proveri dali e pronajdeno teme so pomala cena */
  268.                     else if (minc > distance[j] && distance[j] > 0)
  269.                         minc = distance[k = j];
  270.                 }
  271.             }
  272.             finalno[from = k] = true;
  273.         }
  274.  
  275.         return distance;
  276.  
  277.     }
  278.  
  279.     /*******************************************************************************************************/
  280.  
  281.     @Override
  282.     public String toString() {
  283.         String ret = new String();
  284.         for (int i = 0; i < this.num_nodes; i++)
  285.             ret += adjList[i] + "\n";
  286.         return ret;
  287.     }
  288.     public GraphNode<E> getNode(String ime){
  289.         for(int i=0;i<this.adjList.length;i++){
  290.             if(adjList[i].getInfo().equals(ime)) return adjList[i];
  291.         }
  292.         return null;
  293.     }
  294.  
  295. }
  296. class GraphNodeNeighbor<E> {
  297.     GraphNode<E> node;
  298.     float weight;
  299.  
  300.     public GraphNodeNeighbor(GraphNode<E> node, float weight) {
  301.         this.node = node;
  302.         this.weight = weight;
  303.     }
  304.  
  305.     public GraphNodeNeighbor(GraphNode<E> node) {
  306.         this.node = node;
  307.         this.weight = 0;
  308.     }
  309.  
  310.     @Override
  311.     public boolean equals(Object obj) {
  312.         @SuppressWarnings("unchecked")
  313.         GraphNodeNeighbor<E> pom = (GraphNodeNeighbor<E>)obj;
  314.         return pom.node.equals(this.node);
  315.     }
  316. }
  317. class GraphNode<E> {
  318.     private int index; //index (reden broj) na temeto vo grafot
  319.     private E info;
  320.     private LinkedList<GraphNodeNeighbor<E>> neighbors;
  321.  
  322.     public GraphNode(int index, E info) {
  323.         this.index = index;
  324.         this.info = info;
  325.         neighbors = new LinkedList<GraphNodeNeighbor<E>>();
  326.     }
  327.  
  328.     public boolean containsNeighbor(GraphNode<E> o){
  329.         GraphNodeNeighbor<E> pom = new GraphNodeNeighbor<E>(o,0);
  330.         return neighbors.contains(pom);
  331.     }
  332.  
  333.     public void addNeighbor(GraphNode<E> o, float weight){
  334.         GraphNodeNeighbor<E> pom = new GraphNodeNeighbor<E>(o,weight);
  335.         neighbors.add(pom);
  336.     }
  337.  
  338.     public void removeNeighbor(GraphNode<E> o){
  339.         GraphNodeNeighbor<E> pom = new GraphNodeNeighbor<E>(o,0);
  340.         if(neighbors.contains(pom))
  341.             neighbors.remove(pom);
  342.     }
  343.  
  344.     @Override
  345.     public String toString() {
  346.         String ret= "INFO:"+info+" SOSEDI:";
  347.         for(int i=0;i<neighbors.size();i++)
  348.             ret+="("+neighbors.get(i).node.info+","+neighbors.get(i).weight+") ";
  349.         return ret;
  350.  
  351.     }
  352.  
  353.     public void updateNeighborWeight(GraphNode<E> o, float weight){
  354.         Iterator<GraphNodeNeighbor<E>> i = neighbors.iterator();
  355.         while(i.hasNext()){
  356.             GraphNodeNeighbor<E> pom = i.next();
  357.             if(pom.node.equals(o))
  358.                 pom.weight = weight;
  359.         }
  360.  
  361.     }
  362.  
  363.     @Override
  364.     public boolean equals(Object obj) {
  365.         @SuppressWarnings("unchecked")
  366.         GraphNode<E> pom = (GraphNode<E>)obj;
  367.         return (pom.info.equals(this.info));
  368.     }
  369.  
  370.     public int getIndex() {
  371.         return index;
  372.     }
  373.  
  374.     public void setIndex(int index) {
  375.         this.index = index;
  376.     }
  377.  
  378.     public E getInfo() {
  379.         return info;
  380.     }
  381.  
  382.     public void setInfo(E info) {
  383.         this.info = info;
  384.     }
  385.  
  386.     public LinkedList<GraphNodeNeighbor<E>> getNeighbors() {
  387.         return neighbors;
  388.     }
  389.  
  390.     public void setNeighbors(LinkedList<GraphNodeNeighbor<E>> neighbors) {
  391.         this.neighbors = neighbors;
  392.     }
  393.     class GraphNodeNeighbor<E> {
  394.         GraphNode<E> node;
  395.         float weight;
  396.  
  397.         public GraphNodeNeighbor(GraphNode<E> node, float weight) {
  398.             this.node = node;
  399.             this.weight = weight;
  400.         }
  401.  
  402.         public GraphNodeNeighbor(GraphNode<E> node) {
  403.             this.node = node;
  404.             this.weight = 0;
  405.         }
  406.  
  407.         @Override
  408.         public boolean equals(Object obj) {
  409.             @SuppressWarnings("unchecked")
  410.             GraphNodeNeighbor<E> pom = (GraphNodeNeighbor<E>)obj;
  411.             return pom.node.equals(this.node);
  412.         }
  413.  
  414.     }
  415. }
  416. class Edge{
  417.     private int fromVertex, toVertex;
  418.     private float weight;
  419.     public Edge(int from, int to, float weight){
  420.         this.fromVertex = from;
  421.         this.toVertex = to;
  422.         this.weight = weight;
  423.     }
  424.  
  425.     public int getFrom(){
  426.         return this.fromVertex;
  427.     }
  428.     public int getTo(){
  429.         return this.toVertex;
  430.     }
  431.     public float getWeight(){
  432.         return this.weight;
  433.     }
  434.  
  435.     @Override
  436.     public String toString() {
  437.         return "("+fromVertex+","+toVertex+")="+weight+" ";
  438.     }
  439. }
  440. public class Zeleznici {
  441.     public static void main(String[] args) {
  442.         Scanner input= new Scanner(System.in);
  443.         int brojGradovi= Integer.parseInt(input.nextLine());
  444.         Graph<String> graph= new Graph<>(brojGradovi);
  445.         for(int i=0;i<brojGradovi;i++){
  446.             graph.adjList[i].setIndex(i);
  447.             graph.adjList[i].setInfo(input.nextLine());
  448.         }
  449.         int brojPrugi= Integer.parseInt(input.nextLine());
  450.         for(int i=0;i<brojPrugi;i++){
  451.             String[] info_pruga= input.nextLine().split("\\s+");
  452.             GraphNode<String> city1= graph.getNode(info_pruga[0]);
  453.             GraphNode<String> city2= graph.getNode(info_pruga[1]);
  454.             graph.addEdge(city1.getIndex(),city2.getIndex(),Float.parseFloat(info_pruga[2]));
  455.         }
  456.         String[] info= input.nextLine().split("\\s+");
  457.         String glaven= info[0];
  458.         float budget= Integer.parseInt(info[1]);
  459.         float budget_spent=0;
  460.         List<Edge> le= graph.prim(graph.getNode(glaven).getIndex());
  461.         int counter=0;
  462.         for(Edge e : le){
  463.             if(e.getWeight()>budget) break;
  464.             budget-=e.getWeight();
  465.             budget_spent+=e.getWeight();
  466.             counter++;
  467.         }
  468.         System.out.println((int)budget_spent+" "+counter);
  469.     }
  470. }
  471. /*
  472. 5
  473. Prilep
  474. Bitola
  475. Stip
  476. Veles
  477. Kicevo
  478. 5
  479. Prilep Bitola 10
  480. Veles Stip 12
  481. Bitola Kicevo 15
  482. Veles Prilep 13
  483. Kicevo Prilep 20
  484. ----------------
  485. Prilep 48
  486.  */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement