Solução Informática - Nível Avançado - Semana 6

Solução por Thiago Mota

Conhecimento prévio:;

• Grafos - Flood Fill

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: