Problemas de Programação

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=674&page=show_problem&problem=989 For this problem, we need to generate the Minimum Spanning Tree (MST). Then, for every edge (street) that we use, we need to keep that one that has the biggest value (decibels). import java.io.*; import java.util.*; class Main {     public ArrayList<ArrayList<Edge>> adjList;           public int prim(int start, int end) {         Queue<Edge> queue = new PriorityQueue<>();         queue.add(new Edge(start, 0));                 HashSet<Integer> visited = new HashSet<>();                 int maxSoundIntensity = 0;         while (queue.size() > 0) {             Edge curr = queue.poll();             int currCrossing = curr.crossing;             int currDecibels = curr.decibels;                         if (visited.contains(currCrossing)) {                 continue;             }             visited.a

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=674&page=show_problem&problem=1541 For this problem, we need to generate the Minimum Spanning Tree (MST) to find the minimum cost to connect all the schools. The solution below opted by using Kruskal's algorithm. When we calculate the minimum cost, we need to keep all the edges used for this purpose. Finally, we need to generate a MST for every edge that we considered for the minimum cost, but without using that specific edge. For every minimum cost encountered, we keep the one that is minimum. PS.: It is important to remember that when we are calculating the second minimum cost, we need to check if all the schools are being considered. import java.io.*; import java.util.*; class Main {     public int[] nodeParent;     public int[] depth;         public int root(int n) {         while (n != nodeParent[n]) {             n = nodeParent[n];         }         retur

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2445 The solution below used Dynamic Programming to solve this problem. import java.io.*; import java.util.*; class Main {     public ArrayList<ArrayList<Integer>> garments;     public int[][] matrix;     public int maxMoney;     public int totalMoney;     public int numGarments;         public void rec(int garment, int necessaryMoney) {         if (necessaryMoney > maxMoney) {             return;         }                 if (garment == numGarments) {             totalMoney = Math.max(totalMoney, necessaryMoney);             return;         }                 if (matrix[garment][necessaryMoney] != 0) {             return;         }         matrix[garment][necessaryMoney] = 1;                 for (int i = 0; i < garments.get(garment).size(); i++) {             // go to the next garment considering the ith model of the cu

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=674&page=show_problem&problem=1310 For this problem, we need to generate the Minimum Spanning Tree (MST) through the distances between every pair of node. Next, we transform some vertexes in satellite channels, and we present the remaining edge with the maximum value. import java.io.*; import java.util.*; import java.text.*; class Main {     public int[] nodeParent;     public int[] depth;         public int root(int n) {         while (n != nodeParent[n]) {             n = nodeParent[n];         }         return n;            }         public boolean union(int n1, int n2) {         int rootN1 = root(n1);         int rootN2 = root(n2);                 if (rootN1 != rootN2) {             if (depth[rootN1] >= depth[rootN2]) {                 nodeParent[rootN2] = nodeParent[rootN1];                 if (depth[rootN1] == depth[rootN2]) {                     depth[rootN

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=654&page=show_problem&problem=152 The solution below used Brute Force to solve this problem. import java.io.*; import java.util.*; import java.text.*; class Main {     public Coord[] coords; // keep coordinates of the computers     public double minLength; // minimum length of cable     public double totalLength; // keep the length of each attempt     public int numComputers;     public int[] considered;     public Edge[] edges; // keep the edges used     public Edge[] answer; // keep the best set of edges used     public int index;        public void rec(int x, int y, int numComputersConsidered) {         if (totalLength > minLength) {             return;         }                // if I considered all the computers         if (numComputersConsidered == numComputers) {             minLength = totalLength;             for (int i = 0; i < numComputers-1; i++) {

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=674&page=show_problem&problem=485 Knowing the maximum load that a truck can transport between two given cities, we need to determine the maximum load that can be transported from a start to a destination city. For this reason, the solution below uses a modified Prim's algorithm. Instead of choosing the edges which the weight limit is the minimum, we choose those with the maximum weight limit. Then, we only need to keep which one of these chosen edges has the minimum value. import java.io.*; import java.util.*; class Main {      public ArrayList<ArrayList<Edge>> adjList;         public int prim(int start, int end) {         Queue<Edge> queue = new PriorityQueue<>();         queue.add(new Edge(start, Integer.MAX_VALUE));                HashSet<Integer> visited = new HashSet<>();                int minLoad = Integer.MAX_VALUE;

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=674&page=show_problem&problem=1783 We need to find a path such that the minimum capacity among all of the remaining roads is as large as possible. For this reason, the solution below uses a modified Prim's algorithm. Instead of choosing the edges which the cost is the minimum, we choose those with the maximum cost. Then, we only need to keep which one of these chosen edges has the minimum value (minimum capacity). import java.io.*; import java.util.*; class Main {       public ArrayList<ArrayList<Edge>> adjList;          public int prim(int start, int numNodes) {         Queue<Edge> queue = new PriorityQueue<>();         queue.add(new Edge(start, Integer.MAX_VALUE));                 HashSet<Integer> visited = new HashSet<>();                 int minCost = Integer.MAX_VALUE;         while (queue.size() > 0) {             Edge

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=682&page=show_problem&problem=1112 If you want to see another solution for this problem, click here . As the previous solution, this one also used Floyd-Warshall algorithm to solve this problem. The difference is that this solution has some improvements: We only have one matrix with 3 dimensions. One of them is related to who is young and who is aged 30 or more. We do not use a map structure to map the letters to numbers. It is done simply by decreasing 'A' of the character read. We assume that the maximum number of letters (nodes) is 26 (A-Z). import java.io.*; import java.util.*; class Main {      public final int MAX_SIZE = 26;         public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));                int nu

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=682&page=show_problem&problem=1112 The solution below used Floyd-Warshall algorithm to solve this problem. There are two matrices, one for who is young, and the other one for people aged 30 or more. After filling these matrices, we use Floyd-Warshall to find the minimum cost between every pair of node. Then, for every node, we find which ones of them give us the minimum cost. import java.io.*; import java.util.*; class Main {        public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));                 int numEdges = sc.nextInt();         while (numEdges != 0) {             int[][] matrixY = new int[numEdges*2][numEdges*2];             int[][] matrixM = new int[numEdges*2][numEdges*2];             for (int i = 0; i < numEdge

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=682&page=show_problem&problem=762 This problem asks us to determine the average shortest path length between every pair of nodes. However, first, we need to calculate the shortest path length between every pair of nodes, and it is what the Floyd-Warshall algorithm does. import java.io.*; import java.util.*; class Main {        public int[][] matrix;         public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);                 int numCase = 0;                         int p1 = sc.nextInt();         int p2 = sc.nextInt();         while (p1 != 0 || p2 != 0) {             matrix = new int[100][100];             for (int i = 0; i < 100; i++) {                 for (int j = 0; j < 100; j++) {                     matrix[i][j] = 10000000;                 }                 matrix[i][i] = 0;             }            

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=669&page=show_problem&problem=2021 For this problem, we need to find out if the graph is bipartite. The solution below used a Breath-First Search (BFS) to accomplish this task. import java.io.*; import java.util.*; class Main {       public ArrayList<ArrayList<Integer>> adjList;     public int[] nodes;     public int[] count;        public boolean bfs(int start, int numNodes) {         Queue<Integer> queue = new ArrayDeque<>();         queue.add(start);         nodes[start] = 0;                count[0]++;                while (queue.size() > 0) {             int currNode = queue.poll();                        ArrayList<Integer> reachNodes = adjList.get(currNode);             for (int i = 0; i < reachNodes.size(); i++) {                 if (nodes[reachNodes.get(i)] == -1) {                     nodes[reachNodes.get(i)] = (nodes[cur