TOPIC

PROBLEM 1447 - URI Fórum 1.0

URI Online Judge asked 7 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • Caio Oliveira replied 6 years ago

    isso pode não funcionar as vezes: ao escolher o menor caminho, as vezes vc impossibilita a escolha de outros caminhos médios, que resultaria em uma soma menor. testa esse input:

    5 7
    1 2 1
    2 3 1
    3 5 1
    2 5 3
    1 4 2
    4 3 2
    4 5 100
    2 1

    A resposta tem que ser 9, mas eu acho que seu algorítmo geraria 105

  • Joao G Martinez replied 4 years ago

    Como checar esses caminhos médios? tbm to pegando 10% WA

  • cr.rusucosmin replied 5 years ago

    Is this a mincostmaxflow problem? My algorithm using max flow with min cost is getting tle. Please help!

  • Leonardo Blanger replied 6 years ago

    Obrigado, mas eu já consegui Accept, era exatamente isto. :D

  • Leonardo Blanger replied 6 years ago

    Olá, eu estou tomando Wrong Answer (10%). Não consigo entender o por quê, o meu algoritmo faz o seguinte:

     Enquanto ainda houverem pessoas para viajar e caminhos disponíveis, encontro o caminho de menor custo (Djikstra) em termos de passagem aérea e que ainda possua capacidade de livre (ainda não foi utilizado nenhuma vez).
     Em seguida cancelo a capacidade (k) de todas as arestas deste caminho, e incremento a resposta em:
    resposta += min(pessoas_restantes, k) * custo[n];
      pessoas_restantes -= min(pessoas_restantes, k);
      // custo[n] armazena o caminho de menor custo de 1 a n ainda não usado

    Não entendo o que poderia estar errado.