My T-shirt suits me - UVA 11045
O problema pede para distribuirmos uma camisa para cada voluntário, considerando os tamanhos. Se for possível vamos imprimir YES, caso contrário NO.
Como N e M são pequenos. Poderíamos resolver esse problema fazendo uma busca completa usando backtracking.
Porém, para deixar a solução mais interessante, vamos modelar o problema como um grafo bipartido, onde de um lado teremos as camisas e do outro os voluntários.
Criaremos um nó para cada tamanho de camisa, um nó para cada voluntário, um nó origem e um nó destino.
Criaremos arestas entre o nó de origem e os 6 nós dos tamanhos de camisa.
Criaremos arestas entre os nós dos tamanhos da camisa escolhidos e os respectivos nós dos voluntários.
Criaremos arestas entre os voluntários e o nó destino.
Cada aresta tem capacidade 1.
Depois rodaremos o algoritmo de Ford Fulkerson para encontrar o fluxo máximo. Caso o fluxo máximo seja igual ao número de voluntários, então significa que todos os voluntários foram atendidos e, portanto, existe uma distribuição possível.
Alguns probleminhas que você terá que resolver no seu código?
- Você vai representar o grafo como uma lista de adjacências ou como uma matriz?
- Como, dado o tipo da camisa, você identificará o nó que você usou para representá-la?