Solução por Pedro Michel, comentário de João Guilherme
Esse é um problema clássico de MST, para revisar a matéria veja a aula 17 do curso Noic clicando aqui. Então o que fazemos é calcular a árvore geradora mínima e depois imprimimos o custo total menos o custo da MST (ou seja, quanto vamos economizar).
Segue código para melhor entendimento.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| #define MAX 200010 | |
| using namespace std; | |
| struct aresta | |
| { | |
| int a,b; | |
| int dis; | |
| }; | |
| int pai[MAX]; | |
| aresta grafo[MAX]; | |
| int _find(int a) | |
| { | |
| if(pai[a] == a) | |
| return a; | |
| return pai[a] = _find(pai[a]); | |
| } | |
| void _union(int a, int b) | |
| { | |
| pai[a] = b; | |
| } | |
| bool comp(aresta a, aresta b) | |
| { | |
| return a.dis < b.dis; | |
| } | |
| int Kruskal(int m) | |
| { | |
| int soma = 0; | |
| for(int i = 0; i < m; i++) | |
| { | |
| int a = _find(grafo[i].a); | |
| int b = _find(grafo[i].b); | |
| if(a != b) | |
| { | |
| soma+=grafo[i].dis; | |
| _union(a,b); | |
| } | |
| } | |
| return soma; | |
| } | |
| int main() | |
| { | |
| int n, m; | |
| while(scanf("%d%d", &n, &m) && (n+m)) | |
| { | |
| for(int i = 0; i < n; i++) | |
| pai[i] = i; | |
| int total = 0; | |
| for(int i = 0; i < m; i++) | |
| scanf("%d%d%lld", &grafo[i].a, &grafo[i].b, &grafo[i].dis), total+=grafo[i].dis; | |
| sort(grafo, grafo+m, comp); | |
| printf("%d\n", total - Kruskal(m)); | |
| } | |
| return 0; | |
| } |