Como o fórum comeu minha mensagem e eu não consigo usar
copy-paste nesse formulário, vocês podem ler ela aqui:
http://www.ime.usp.br/~mh/regras.txt
Leiam com atenção, sigam tudo rigorosamente e perdoem os
prováveis erros de português que vão encontrar.
In reply to Marcelo Hashimoto
Re: IMPORTANTE: regras obrigatórias para a TAREFA 6
Olá, Marcelo.
Acho que já sei a resposta, mas vou perguntar mesmo assim (
> Observação importante: não podem haver linhas em branco
> na saída
Mas, pode haver uma quebra de linha após a última linha de texto, né?
Obrigado.
Igor.
In reply to Igor Ribeiro Sucupira
Re: IMPORTANTE: regras obrigatórias para a TAREFA 6
by Marcelo Hashimoto -
Obrigado, eu havia me esquecido disso.
Então, repetindo para quem não leu a mensagem do Igor:
a única linha em branco que a saída deve ter é a última linha.
Então, repetindo para quem não leu a mensagem do Igor:
a única linha em branco que a saída deve ter é a última linha.
In reply to Marcelo Hashimoto
Re: IMPORTANTE: regras obrigatórias para a TAREFA 6
Como é tratado o caso em que existem múltiplos fluxos máximos?
Qualquer resposta vale? Se sim, o diff sozinho não consegue verificar se a solução é válida. Se não, como podemos ter certeza de que nosso programa irá gerar a mesma reposta do gabarito?
Qualquer resposta vale? Se sim, o diff sozinho não consegue verificar se a solução é válida. Se não, como podemos ter certeza de que nosso programa irá gerar a mesma reposta do gabarito?
In reply to Fabio Alexandre Campos Tisovec
Re: IMPORTANTE: regras obrigatórias para a TAREFA 6
Talvez o Marcelo vá utilizar apenas instâncias que só possuem uma solução.
Caso contrário, acho que, para começar, ele teria de implementar um programa que recebe uma instância e uma solução e verifica se a solução é válida (os arcos existem, o fluxo é um (s,t)-fluxo, o valor do fluxo é mesmo o indicado na linha que começa com 's', as capacidades são respeitadas etc.).
Abraços.
Igor.
In reply to Igor Ribeiro Sucupira
Re: IMPORTANTE: regras obrigatórias para a TAREFA 6
by Marcelo Hashimoto -
O Igor está certo. Caso eu descubra que as instâncias
utilizadas permitem mais do que um fluxo máximo, eu
utilizarei um script que verifica a corretudo do fluxo.
Em outras palavras: não se preocupem com isso.
utilizadas permitem mais do que um fluxo máximo, eu
utilizarei um script que verifica a corretudo do fluxo.
Em outras palavras: não se preocupem com isso.
In reply to Marcelo Hashimoto
Re: IMPORTANTE: regras obrigatórias para a TAREFA 6
by Daniel Ribeiro -
Algumas perguntas sobre esta tarefa:
- Se for feito em C, precisa ser ansi?
- Podemos usar o fato de que as instâncias que você utilizará terão no máximo 5000 (cinco mil) vértices e 500000 (quinhentos mil) arcos?
- Qual é a relevância da eficiência na correção? Ou seja, há um limite mínimo de quanto eficiente um programa deve ser?
- Se for feito em C, precisa ser ansi?
- Podemos usar o fato de que as instâncias que você utilizará terão no máximo 5000 (cinco mil) vértices e 500000 (quinhentos mil) arcos?
- Qual é a relevância da eficiência na correção? Ou seja, há um limite mínimo de quanto eficiente um programa deve ser?
In reply to Daniel Ribeiro
Re: IMPORTANTE: regras obrigatórias para a TAREFA 6
by Marcelo Hashimoto -
1) Não, não precisa ser em ansi puro.
2) Sim, foi por isso que "revelei" o tamanho das instâncias nas regras.
Se quiser fazer algo como alocar uma matriz de incidência 5000x5000
porque é mais eficiente ou simples de implementar, esteja à vontade.
Mas tome cuidado para não estourar o MAXINT ou algo parecido.
3) Ainda não defini exatamente como a eficiência influenciará na nota.
Tente fazer o melhor possível. Se seu programa for de fato uma
implementação polinomial do preflow-push, ele certamente receberá
nota alta.
2) Sim, foi por isso que "revelei" o tamanho das instâncias nas regras.
Se quiser fazer algo como alocar uma matriz de incidência 5000x5000
porque é mais eficiente ou simples de implementar, esteja à vontade.
Mas tome cuidado para não estourar o MAXINT ou algo parecido.
3) Ainda não defini exatamente como a eficiência influenciará na nota.
Tente fazer o melhor possível. Se seu programa for de fato uma
implementação polinomial do preflow-push, ele certamente receberá
nota alta.
In reply to Marcelo Hashimoto
Re: IMPORTANTE: regras obrigatórias para a TAREFA 6
Marcelo, meu programa supõe que a última linha de entrada, por exemplo, a 2 3 10, termina com um \n.
Eu quero saber se posso deixar assim, ou se tenho que tratar os casos em que a última linha não termine com um \n?
muito obrigado,
Antonio José.
Eu quero saber se posso deixar assim, ou se tenho que tratar os casos em que a última linha não termine com um \n?
muito obrigado,
Antonio José.
In reply to Antonio José Gonzales Alves
Re: IMPORTANTE: regras obrigatórias para a TAREFA 6
by Marcelo Hashimoto -
Pode supor que isso é verdade.
Usarei apenas entradas em que a
última linha termina com um '\n'.
Usarei apenas entradas em que a
última linha termina com um '\n'.
In reply to Marcelo Hashimoto
Re: IMPORTANTE: regras obrigatórias para a TAREFA 6
by Daniel Ribeiro -
Caso as instâncias não tenham solução (que é o caso de fontes e sorvedouros em componentes conexas distintas), como fica a saída? Não colocamos a linha 's VALUE'? Mostramos os nós que ficaram com excesso diferente de 0? Avisamos que não foi possível mandar todo o fluxo com um comentário?
In reply to Daniel Ribeiro
Re: IMPORTANTE: regras obrigatórias para a TAREFA 6
by Marcelo Hashimoto -
Instâncias de fluxo máximo sempre admitem uma
solução viável, que é o fluxo nulo. Atribuir zero a
todos os arcos sempre resulta em um fluxo válido.
Então não existem instâncias sem solução.
solução viável, que é o fluxo nulo. Atribuir zero a
todos os arcos sempre resulta em um fluxo válido.
Então não existem instâncias sem solução.
In reply to Marcelo Hashimoto
Re: IMPORTANTE: regras obrigatórias para a TAREFA 6
by Daniel Ribeiro -
É verdade. Tava confundindo os problemas.