Advertisement
dzocesrce

[APS] SnowStorm

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