Advertisement
dzocesrce

[APS] Ministry of Transport & Communications

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