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++
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; } |
