Advertisement
dzocesrce

[APS] Floods

Aug 29th, 2023
279
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 16.68 KB | None | 0 0
  1. // juni 2023, za povisoka ocenka
  2.  
  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.  
  442. }
  443.  
  444. public class Poplavi {
  445.     public static void main(String[] args) {
  446.         Scanner input= new Scanner(System.in);
  447.         int numCities= Integer.parseInt(input.nextLine());
  448.         int numPaths= Integer.parseInt(input.nextLine());
  449.         int recoveredPaths= Integer.parseInt(input.nextLine());
  450.         Graph<String> graph= new Graph<>(numCities);
  451.         for(int i=0;i<numCities;i++){
  452.             graph.adjList[i].setIndex(i);
  453.             graph.adjList[i].setInfo(input.nextLine());
  454.         }
  455.         for(int i=0;i<numPaths;i++){
  456.             String[] info_path= input.nextLine().split("\\s+");
  457.             GraphNode<String> city1= graph.getNode(info_path[0]);
  458.             GraphNode<String> city2= graph.getNode(info_path[1]);
  459.             graph.addEdge(city1.getIndex(),city2.getIndex(),Float.parseFloat(info_path[2]));
  460.         }
  461.         for(int i=0;i<recoveredPaths;i++){
  462.             String[] info_path= input.nextLine().split("\\s+");
  463.             GraphNode<String> city1= graph.getNode(info_path[0]);
  464.             GraphNode<String> city2= graph.getNode(info_path[1]);
  465.             graph.deleteEdge(city1.getIndex(),city2.getIndex());
  466.             graph.addEdge(city1.getIndex(),city2.getIndex(),0);
  467.         }
  468.  
  469.     List<Edge> list_edges= graph.kruskal();
  470.         int counter_paths=0;
  471.         float counter_weight=0;
  472.         for(Edge e: list_edges){
  473.             if(e.getWeight()>0){
  474.                 counter_paths++;
  475.                 counter_weight+=e.getWeight();
  476.             }
  477.         }
  478.         System.out.println(counter_paths+" "+(int)counter_weight);
  479.         for(Edge e: list_edges){
  480.             if(e.getWeight()>0){
  481.                 System.out.println(graph.adjList[e.getFrom()].getInfo()+" "+graph.adjList[e.getTo()].getInfo());
  482.             }
  483.         }
  484.     }
  485. }
  486. /*
  487. Input:
  488. 5
  489. 6
  490. 3
  491. Skopje
  492. Kumanovo
  493. SvetiNikole
  494. Veles
  495. Stip
  496. Skopje Veles 5
  497. Skopje Kumanovo 3
  498. Skopje SvetiNikole 6
  499. Kumanovo SvetiNikole 4
  500. Stip Veles 4
  501. Stip SvetiNikole 2
  502. Skopje SvetiNikole
  503. Stip SvetiNikole
  504. Kumanovo SvetiNikole
  505. Output:
  506. 1 4
  507. Veles Stip
  508. -----------
  509. Input:
  510. 5
  511. 6
  512. 0
  513. Skopje
  514. Kumanovo
  515. SvetiNikole
  516. Veles
  517. Stip
  518. Skopje Veles 5
  519. Skopje Kumanovo 3
  520. Skopje SvetiNikole 6
  521. Kumanovo SvetiNikole 4
  522. Stip Veles 4
  523. Stip SvetiNikole 2
  524. Output:
  525. 4 13
  526. SvetiNikole Stip
  527. Skopje Kumanovo
  528. Kumanovo SvetiNikole
  529. Veles Stip
  530. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement