URI - 1148 - Países em Guerra - Grafos - C++

Plataforma: URI
Problema: 1148

Enunciado:

No ano 2050, após diversas tentativas da ONU de manter a paz no mundo, explode a terceira guerra mundial. Segredos industriais, comerciais e militares obrigaram todos os países a utilizar serviços de espionagem extremamente sofisticados, de forma que em cada cidade do mundo há ao menos um espião de cada país. Esses espiões precisam se comunicar com outros espiões, com informantes e mesmo com as suas centrais durante as suas ações. Infelizmente não existe uma forma segura de um espião se comunicar em um período de guerra, então as mensagens são sempre enviadas em código para que somente o destinatário consiga ler a mensagem e entender o seu significado.
Os espiões utilizam o unico serviço que funciona no período de guerra, os correios. Cada cidade possui uma agência postal onde as cartas são enviadas. As cartas podem ser enviadas diretamente ao seu destino ou a outras agências postais, até que a carta chegue à agência postal da cidade de destino, se isso for possível.
Uma agência postal na cidade A pode enviar diretamente uma carta impressa para a agência postal da cidade B se houver um acordo de envio de cartas, que determina o tempo, em horas, que uma carta leva para chegar da cidade A à cidade B (e não necessariamente o contrário). Se não houver um acordo entre as agências A e B, a agência A pode tentar enviar a carta a quantas agências for necessário para que a carta chegue ao seu destino, se isso for possível.
Algumas agências são interligadas por meios eletrônicos de comunicação, como satélites e fibras ópticas. Antes da guerra, essas ligações atingiam todas as agências, fazendo com que uma carta fosse enviada de forma instantânea, mas durante o período de hostilidades cada país passou a controlar a comunicação eletrônica e uma agência somente pode enviar uma carta a outra agência por meio eletrônico (ou seja, instantaneamente) se ela estiver no mesmo país. Duas agências, A e B, estão no mesmo país se houver uma forma de uma carta impressa enviada de uma das agências ser entregue na outra agência.
O serviço de espionagem do seu país conseguiu obter o conteúdo de todos os acordos de envios de mensagens existentes no mundo e deseja descobrir o tempo mínimo para se enviar uma carta entre diversos pares de cidades. Você seria capaz de ajudá-lo?

Linguagem: C++

Solução:
Neste problema foi utilizado o algoritmo de Floyd Warshall para resolver a solução.
Antes de aplicar o algoritmo, quando o grafo está sendo montado é verificado se há um caminho ligando o ponto a ao ponto b e também o ponto b ao ponto a, para quaisquer pontos a e b. Neste caso, é colocado a distancia 0 entre eles, visto que o problema permite deslocamento sem custo.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

#include <iostream> #include <vector> using namespace std; vector< vector <int> > graph; #define INF 1000000 void floyd_warshall(){ int i, j, k; for (k = 0; k < graph.size(); k++) { for (i = 0; i < graph.size(); i++) { for (j = 0; j < graph.size(); j++) { if (graph[i][k] + graph[k][j] < graph[i][j]){ graph[i][j] = graph[i][k] + graph[k][j]; } } } } } int main() { int V,E,s,d,w; while(true){ cin >> V >> E; if(V==0 and E==0) return 0; graph.clear(); graph.resize(V); for(int i = 0 ; i < V ; ++i) { graph[i].resize(V); } for(int i =0; i< graph.size(); i++){ for(int j =0; j< graph.size(); j++){ graph[i][j]= INF; } } for(int i=0; i<E; i++){ cin >> s >> d >> w; if(graph.at(d-1).at(s-1)==INF){ graph.at(s-1).at(d-1) = w; } else{ graph.at(s-1).at(d-1) = 0; graph.at(d-1).at(s-1) = 0; } } floyd_warshall(); int n; cin >> n; while(n--){ cin >> s >> d; if(graph.at(s-1).at(d-1)<INF and graph.at(d-1).at(s-1)<INF){ cout << 0 << endl; } else{ if(graph.at(s-1).at(d-1)<INF){ cout << graph.at(s-1).at(d-1) << endl; } else{ cout << "Nao e possivel entregar a carta" << endl; } } } cout << endl; } return 0; }

URI - 1152 - Estradas Escuras - Grafos - C++

Plataforma: URI
Problema: 1152

Enunciado: 

Nestes dias se pensa muito em economia, mesmo em Byteland. Para reduzir custos operacionais, o governo de Byteland decidiu otimizar a iluminação das estradas. Até agora, todas as rotas eram iluminadas durante toda noite, o que custava 1 Dólar Byteland por metro a cada dia. Para economizar, eles decidiram não iluminar mais todas as estradas e desligar a iluminação de algumas delas. Para ter certeza que os habitantes de Byteland continuem a se sentirem seguros, eles querem otimizar o sistema de tal forma que após desligar a iluminação de algumas estradas à noite, sempre existirá algum caminho iluminado de qualquer junção de Byteland para qualquer outra junção.

Qual é a quantidade máxima de dinheiro que o governo de Byteland pode economizar, sem fazer os seus habitantes sentirem-se inseguros?

Linguagem: C++

Solução:
Este é um problema clássico de grafos chamado Minimal Spanning Tree. Para solucionar este problema foi utilizado o algoritmo clássico de Kruskal. A ideia deste algoritmo é ordenar todas as arestas e ir colocando das menores para as maiores no grafo final. Se ao colocar uma das arestas o grafo resultar em um grafo ciclico, então esta aresta não é colocada.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

#include <iostream> #include <vector> #include <algorithm> #include <utility> using namespace std; struct Graph { int V, E; vector< pair<int, pair<int, int> > > edges; Graph(int V, int E) { this->V = V; this->E = E; } void addEdge(int u, int v, int w) { edges.push_back(make_pair(w, make_pair(u, v))); } int kruskalMST(); }; struct DisjointSets { int *parent, *rnk; int n; DisjointSets(int n) { this->n = n; parent = new int[n+1]; rnk = new int[n+1]; for (int i = 0; i <= n; i++) { rnk[i] = 0; parent[i] = i; } } int find(int u) { if (u != parent[u]) parent[u] = find(parent[u]); return parent[u]; } void merge(int x, int y) { x = find(x), y = find(y); if (rnk[x] > rnk[y]) parent[y] = x; else parent[x] = y; if (rnk[x] == rnk[y]) rnk[y]++; } }; int Graph::kruskalMST() { int mst_wt = 0; sort(edges.begin(), edges.end()); DisjointSets ds(V); vector< pair<int, pair<int, int> > >::iterator it; for (it=edges.begin(); it!=edges.end(); it++) { int u = it->second.first; int v = it->second.second; int set_u = ds.find(u); int set_v = ds.find(v); if (set_u != set_v) { mst_wt += it->first; ds.merge(set_u, set_v); } } return mst_wt; } int main() { int V, E, s, d, weight; V=1;E=1; while(true){ cin >> V; cin >> E; if(V==0 and E==0) break; Graph g(V, E); int total_weight = 0; for(int i=0;i<E;i++){ cin >> s >> d >> weight; g.addEdge(s,d,weight); total_weight = total_weight + weight; } int mst_wt = g.kruskalMST(); cout << total_weight - mst_wt << endl; } return 0; }

URI - 1195 - Árvore Binária de Busca - Grafos - C++

Plataforma: URI

Problema: 1195

Enunciado:

Em computação, a árvores binária de busca ou árvore binária de pesquisa é uma estrutura baseada em nós (nodos), onde todos os nós da subárvore esquerda possuem um valor numérico inferior ao nó raiz e todos os nós da subárvore direita possuem um valor superior ao nó raiz (e assim sucessivamente). O objetivo desta árvore é estruturar os dados de forma flexível, permitindo a busca binária de um elemento qualquer da árvore.

A grande vantagem das árvores de busca binária sobre estruturas de dados convencionais é que os algoritmos de ordenação (percurso infixo) e pesquisa que as utilizam são muito eficientes.

Para este problema, você receberá vários conjuntos de números e a partir de cada um dos conjuntos, deverá construir uma árvore binária de busca. Por exemplo, a sequência de valores: 8 3 10 14 6 4 13 7 1 resulta na seguinte árvore binária de busca:

                    8

         3               10

     1       6                14

           4     7         13
Linguagem: C++

Solução:
Primeiramente dividimos a solução em três partes:
1) Criar a estrutura da árvore:
Foi criado uma struct TreeNode. Ele contem um ponteiro para o lado esquerdo, um ponteiro para o lado direito e um valor.
Além disso, foi feito um construtor que coloca NULL em seus dois ponteiros e coloca o valor a ser inserido na estrutura.

2) Inserir os elementos na árvore:
Para inserir o elemento na árvore, é verificado a posição em que deve ser inserido. Se o valor for menor do que o valor que está no nodo atual, então o processo é refeito verificando o nodo a esquerda. Caso o valor a ser inserido for maior que o nodo atual, o processo é refeito verificando o nodo a direita. Quando for encontrado um nodo NULL, então o elemento é inserido.

3) Imprimir a árvore:
É preciso imprimir nas três ordens citadas pelo exercício. A função de imprimir foi feito de forma recursiva, determinando o que deve ser impresso de acordo com a ordem escolhida.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83

#include <iostream> using namespace std; struct TreeNode{ TreeNode * left; TreeNode * right; int value; TreeNode(int newValue) { value = newValue; left = NULL; right = NULL; } }; void insert(TreeNode* & root, int newValue){ if(root == NULL){ root = new TreeNode( newValue ); return; } if(newValue > (root->value) ){ insert(root->right, newValue); } else{ insert(root->left, newValue); } return; } // order : 1 - pre, 2 - in, 3 - post void printTree(TreeNode* & root, bool first, int order){ if(root == NULL){ return; } if(first){ switch(order){ case 1: cout << "Pre.:"; break; case 2: cout << "In..:"; break; case 3: cout << "Post:"; break; } } switch(order){ case 1: // pre order cout << " " << root->value; printTree(root->left,false,order); printTree(root->right, false,order); break; case 2: // in order printTree(root->left,false,order); cout << " " << root->value; printTree(root->right, false,order); break; case 3: // post order printTree(root->left,false,order); printTree(root->right, false,order); cout << " " << root->value; break; } if(first){ cout << endl; } } int main(){ int n, elements, value; cin >> n; for(int i = 1;i<=n; i++){ TreeNode * root = NULL; cout << "Case " << i << ":" <<endl; cin >> elements; while(elements--){ cin >> value; insert(root, value); } for(int order = 1; order<=3; order++){ printTree(root, true, order); } delete root; cout << endl; } return 0; }