Descreva com precisão o algoritmo e as estruturas de dados (registros, listas ou grafo) para um programa que…

Questão

Descreva com precisão o algoritmo e as estruturas de dados (registros, listas ou grafo) para um programa que organiza caronas entre estudantes: cada viagem tem motorista, capacidade e horário; alunos solicitam vagas em viagens compatíveis com seu horário. O programa deve atribuir passageiros maximizando o número de alunos atendidos, sem alocar um aluno a mais de uma viagem no mesmo horário, e produzir a lista de passageiros por viagem.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Modelo de solução: 1) Representação de dados: registro Viagem {id, motorista, capacidade, horario}; registro Aluno {id, nome, horarios_disponiveis, pedidos}. 2) Construção do grafo bipartido: nós à esquerda = alunos; nós à direita = viagens. Adicionar aresta aluno?viagem se o horário da viagem é compatível com a disponibilidade do aluno e se o aluno solicitou essa viagem. 3) Tratar capacidade das viagens: transformar cada viagem em um nó com capacidade igual ao número de vagas, ou modelar viagem?sumidouro com capacidade = capacidade. 4) Transformação para fluxo: criar fonte conectada a cada aluno com capacidade 1; arestas aluno?viagem com capacidade 1; arestas viagem?sumidouro com capacidade = capacidade da viagem. 5) Algoritmo de otimização: aplicar algoritmo de fluxo máximo (por exemplo Dinic ou Edmonds–Karp) para obter o emparelhamento que maximiza o número de alunos atendidos. Alternativa heurística: ordenar pedidos por prioridade e preencher vagas sequencialmente (menor garantia ótima). 6) Pós-processamento: a partir do fluxo, para cada viagem listar os alunos com aresta aluno?viagem saturada; gerar registros de saída por viagem. 7) Complexidade e justificativa: construção do grafo leva O(V+E); fluxo máximo com Dinic tem complexidade polinomial (depende de E e V) e garante solução ótima que respeita capacidades e restrição de um aluno por horário. Observações de implementação: usar listas de adjacência para o grafo, registros para viagens e alunos, e estruturas de fila para BFS/DFS no algoritmo de fluxo; validar horários e conflitos antes de criar arestas para reduzir E.

Explicação

A solução proposta utiliza uma representação eficiente dos dados e um grafo bipartido para modelar a relação entre alunos e viagens, permitindo a aplicação de algoritmos de fluxo máximo para otimizar a alocação de passageiros. A transformação das viagens em nós com capacidade e a conexão com uma fonte e um sumidouro garantem que as restrições de capacidade e horários sejam respeitadas. Além disso, a complexidade do algoritmo é abordada, assegurando que a solução seja viável em termos de desempenho.

Raio-X da questão

Questões parecidas com resolução

• Em um relatório de erros, foram contabilizados: Erro1 5 ocorrências, Erro2 8 ocorrências, Erro3 7 ocorrências. Qual a…
• Em uma usina, cada estado de uma turbina é registrado com um código de dois bits: | Estado | Código | |---|---| | Parada…
• No controle de um satélite, um gráfico de barras descrito pela equipe registra: com o sistema operacional iniciado, o…
• Em uma estação ambiental, um sistema gera alerta quando a chuva registrada é de pelo menos 20 mm. A equipe muda essa…
• Um sistema de cópia de segurança avisa quando o celular tem menos de 4 GB de espaço livre. Em uma atualização, o limite…
• Em um sistema de agendamento, a instrução é: “Se o campo de telefone estiver vazio, não concluir o cadastro e solicitar…

Todas as questões de Programação - Linguagem de programação