Solução por João Guilherme
Isso é uma questão de grafos, onde o maior desafio é notar qual o grafo. Nesse caso podemos colocar os vértices como sendo a cidade e quanto o pai comprou para cada filho, então ligamos cada vértices aos vértices que ou mantêm quanto ele comprou constante e mudam de cidade ou então para os vértices onde ele continua na mesma cidade mas comprou o presente dessa cidade. Por fim, para cada vértice salvamos a menor diferença numa global e a imprimimos no final do código.
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> | |
| using namespace std; | |
| vector <int> adj[32]; | |
| int type[32], t, w[32], ans = (1 << 20), mark[32][128][128]; | |
| int dfs(int u, int a, int b){ | |
| int v; | |
| mark[u][a][b] = 1; | |
| ans = min(ans, abs(a - b) + (a + b == 0)*(1 << 20)); | |
| for(int i = 0; i < adj[u].size(); ++i){ | |
| v = adj[u][i]; | |
| if(!mark[v][a][b]) | |
| dfs(v, a, b); | |
| } | |
| for(int i = 1; 1; ++i){ | |
| if(a + b + i*w[u] > t) break; | |
| if(type[u] == 0){ | |
| if(!mark[u][a + i*w[u]][b]) | |
| dfs(u, a + i*w[u], b); | |
| } | |
| else{ | |
| if(!mark[u][a][b + i*w[u]]) | |
| dfs(u, a, b + i*w[u]); | |
| } | |
| } | |
| return ans; | |
| } | |
| int main(){ | |
| char tp; | |
| int n, lixo, val, id, k, u; | |
| scanf("%d %d", &n, &t); | |
| for(int i = 0; i < n; ++i){ | |
| scanf("%d %d %c %d", &id, &val, &tp, &k); | |
| type[id] = (tp - 'A'); | |
| w[id] = val; | |
| for(int i = 0; i < k; ++i){ | |
| scanf("%d", &u); | |
| adj[id].push_back(u); | |
| } | |
| } | |
| cout << dfs(0, 0, 0) << "\n"; | |
| return 0; | |
| } |