Solução por Thiago Mota
Conhecimento prévio:;
A primeira observação que temos é que como queremos separar em componentes de soma 0 é necessário que a soma total das componentes seja 0, pois se a soma total for diferente de 0 não existe maneira de dividir as componentes.
Imagine que nós removemos uma aresta e dividimos em duas componentes, a única soma possível de cada componente isolada também deve ser 0, pois se a soma das componentes isoladas forem diferente de 0 não existe maneira de divir em componentes menores com soma 0.
Então, temos que remover arestas de forma que a soma sempre se mantenha 0, para isso basta escolher qualquer aresta que a soma das componentes resultantes continue sendo 0. Como o problema é de minimizar o custo, basta escolher as k arestas de menor custo que mantenha a soma sendo 0 após a remoção dela. Segue o código:
| #include <bits/stdc++.h> | |
| using namespace std; | |
| typedef pair<int, int> pii; | |
| const int maxn = 1e5 + 10; | |
| int n, k, custo[maxn]; | |
| vector<pii> grafo[maxn]; | |
| vector<int> arestas; // Arestas que podem ser removidas | |
| int soma[maxn]; // Soma das componentes | |
| void dfs(int u, int p) { | |
| soma[u] = custo[u]; | |
| for (int i = 0; i < (int)grafo[u].size(); i++) { | |
| int v = grafo[u][i].first, peso = grafo[u][i].second; | |
| if (v == p) // Se o vizinho for o pai, ignorar ele. | |
| continue; | |
| dfs(v, u); | |
| if (soma[v] == 0) // Se a soma da componente for 0, podemos remover essa aresta. | |
| arestas.push_back(peso); // Guardaremos no vetor de arestas removiveis. | |
| soma[u] += soma[v]; | |
| } | |
| } | |
| int main() { | |
| cin >> n >> k; | |
| int soma_custo = 0; | |
| for (int i = 1; i <= n; i++) | |
| cin >> custo[i], soma_custo += custo[i]; | |
| if (soma_custo != 0) { | |
| cout << "-1\n"; | |
| return 0; | |
| } | |
| for (int i = 1; i < n; i++) { | |
| int a, b, c; | |
| cin >> a >> b >> c; | |
| grafo[a].push_back({b, c}); | |
| grafo[b].push_back({a, c}); | |
| } | |
| dfs(1, 0); | |
| sort(arestas.begin(), arestas.end()); // Ordenando as arestas removiveis e pegando as k primeiras. | |
| if ( arestas.size() < k ) { | |
| cout << "-1\n"; | |
| return 0; | |
| } | |
| int ans = 0; | |
| for (int i = 0; i < k; i++) | |
| ans += arestas[i]; | |
| cout << ans << "\n"; | |
| return 0; | |
| } |
by