A primeira capital do Brasil foi Salvador, atualmente capital do estado da Bahia. Na época da colonização, essa cidade foi escolhida devido ao seu perfil geográfico e portuário, que facilitava o transporte de mercadoria e pessoas. A escolha de outras capitais para cada estado, já no período republicano, não foi diferente. Cada capital tem uma característica especial que a fez ser escolhida como referência em âmbito estadual.

Para ajudar a escolher a capital, podemos associar um número, chamado de fator de centralidade, a cada cidade de um estado. Esse número é calculado a partir das diversas linhas de acesso que compõem o sistema de transporte do estado, levando-se em consideração dois aspectos:

• A cidade precisa dar acesso à maioria das cidades do estado. Assim, quanto mais cidades podem ser acessadas pelo sistema de transporte, mais adequada é a cidade para se tornar uma capital.

• A cidade deve servir uma fração consideravel da população do estado. Se mais pessoas podem acessar os serviços de uma cidade, então ela é mais adequada para escolhida como capital.

Para calcular o fator de centralidade de uma cidade $u$, denotado por $C_{u}$, é preciso conhecer as distancias de $u$ a cada cidade alcançável do estado, $v$, denotada por $dist(u,v)$. A distância a cada cidade $v$ é ponderada por sua população, $p_v$. O fator de centralidade é definido como a média ponderada das distâncias. Mais precisamente, se $A_u$ é o conjunto de cidades alcançáveis a partir de $u$, então o fator de centralidade é:

$$ C_{u}=\frac{\sum_{v \in A_u}{p_v \cdot dist(u,v)}}{\sum_{v \in A_u}p_v} $$

Por exemplo, na figura abaixo, as caixas contêm as populações das cidades e cada linha representa um percurso de comprimento mínimo.

O fator de centralidade de Teresina é

$$ C_{Teresina} = \frac{2000 \cdot 0 + 500 \cdot 100 + 1000 \cdot 50}{2000 + 500 + 1000} = 28{,}57 $$

A capital ideal é a cidade que dá acesso a pelo menos metade da população do estado com menor fator de centralidade. Sua tarefa é implementar um programa def_capitais.c que calcula esse fator para cada cidade e as ordena.

Entrada

A entrada contém, na primeira linha, o número de cidades do estado. A partir da segunda, contém cada cidade e sua respectiva população. Depois disso, cada linha representa uma ligação direta entre duas cidades, contendo os nomes e a distância (valores reais) entre elas. O nome de cada cidade tem menos que 50 caracteres e não tem espaços.

Exemplo de entrada

4
Teresina 2000
Parnaiba 500
Floriano 1000
Oeiras 1500
Teresina Parnaiba 100.0
Teresina Floriano 50.0
Parnaiba Floriano 200.0

Saída

A saída deverá exibir um relatório com as cidades que alcançam pelo menos metade da população e os fatores de centralidade associados. As cidades devem ser ordenadas pelo fator de centralidade e, se houver empate, pelo nome.

Exemplo de saída

Teresina 28.57
Floriano 50.00
Parnaiba 100.00

Critérios

É obrigatório utilizar um grafo para representação do estado e as ligações entre as cidades.

Correção

Esta tarefa será corrigida automaticamente sempre que você realizar um git push. Depois de terminada a tarefa, deve-se utilizar o botão na interface de notas para solicitar a correção de um monitor.

Turma AB: O peso desta tarefa é 5.

← Anterior Voltar