1076 - Problem 1076 - uri fórum 1.0 - URI Online Judge
+ 3.0 POINTS
PROBLEM 1076 - URI Fórum 1.0
Domitila Crispim Pietropaolo replied 5 years ago
int c=0, cn=0;
vector< vector <int> > grf;
int a, s, d, f, n, v, ar ;
void dfs ( int vi){
visit[vi]=true;
for ( int e=0; e<grf[vi].size(); e++){
int x=grf[vi][e];
if ( !visit[x]){
grf.resize(10000);
scanf ("%d%d", &v, &ar);
while( ar--){
scanf ("%d %d", &f, &d);
grf[f].push_back(d);
grf[d].push_back(f);
for ( int yo=0; yo<v; yo++){
sort (grf[yo].begin(), grf[yo].end());
memset ( visit, false, sizeof(visit));
printf ("%d\n", cn);
for ( int y=0; y<v; y++){
grf[y].clear();
grf.clear();
RUNTIME <3 me ajudem ;-;
Neilor Tonin [UOJ] replied 7 years ago
Peço desculpas ao inconveniente deste problema, mas o objetivo foi exatamente dificultar a utilização da fórmula, para que utilizassem a busca em profundidade. Na descrição, final do segundo parágrafo, o texto:
... Se existir uma entrada 4 1, isso não impede a existência de outra entrada 1 4 no mesmo caso de teste, ou seja, outra linha ligando estes mesmos dois nodos. De qualquer forma isto não fará diferença no desenho do labirinto, pois se Pedro traçar as duas linhas entre 1 e 4 ou apenas uma delas, a quantidade de movimentos deverá ser a mesma.
Ou seja, isso não caracteriza um ciclo, pois a definição de ciclo seria um passeio de tamanho 3, mas não permite a utilização da fórmula.
Ao invés de iniciar seu grafo com 10000, inicie ele após ler o número de vertices e arestas, dentro do while, inicie seu grafo com o número de vertices.
grf.resize(v);
Pedro Porfirio Muniz Farias replied 5 years ago
Seja D a quantidade de ocorrência de arestas duplicadas. Como se trata de uma árvore não é suficiente calcular 2*(A- D)? Funcionou nos exemplos que executei localmente mas, ao submeter, tomei um WA.
Dâmi Henrique replied 7 years ago
Passou, era simplesmente um for começando em 1, quando deveria começar em 0... Mesmo assim, obrigado! =)
Wyllian Brito replied 7 years ago
Sua lógica está certa, talvez seja problema com a implementação mesmo. Posta seu código pra gente ver.
Eu usei a mesma ideia do Jean, no post lá em cima, fiz uma busca em profundidade p pegar o número de arestas e multipliquei por 2 p contar o caminho de volta... Mas estou recebendo w.a..
Algo a mais que devo considerar? Ou algum caso de teste que me ajude seria bem vindo.. Obrigado
Obrigado pela correção Hades,
Aterei a linha que continha deve traçar.
Assim como você, peço aos demais que confiram para ver se o texto ficou mais claro e por favor, se tiverem sugestões para melhorá-lo, são bem-vindas.
Gabriel Dalalio replied 7 years ago
Totalmente zuado o problema, a resposta seria 2*A mesmo se não tivessem entradas com arestas repetidas
Pra que alguém põe um problema desse no portal? Só se for pra trollar, num é possível...
Hades replied 7 years ago
Também estou com problemas nessa questão. Se o labirinto não possui ciclos o grafo resultante é uma árvore e a resposta deveria ser A2. Poderíamos pensar que o conjunto de arcos dados não são todos usados (o que mudaria a solução), mas existe o seguinte texto no problema: "Uma quantidade A de linhas vem a seguir, cada uma descrevendo um segmento de linha que você devetraçar para desenhar o labirinto desejado". Outro trecho indica que a caneta não pode ser retirada do papel: "Pedro decidiu que não é permitido levantar a caneta do papel"*. Isso mostra que a formulação do problema está confusa.
Aos mantenedores do sistema: Por favor deixem mais claro o enunciado do problema para que possamos resolvê-lo.
Obrigado. Hades
Eu mandei isso quando eu li o problema pela primeira vez ("opa, eu posso simplesmente ignorar 90% da entrada?"). O único jeito disso estar errado é que devem ter casos de teste na entrada que não são conexos (o que, a meu ver, não faz sentido com o enunciado, já que desse jeito ele não conseguiria desenhar o labirinto).
Julio Batista Silva replied 8 years ago
Eu consegui resolver com DFS, mas fiquei pensando se não tinha uma forma ainda mais simples.
Alguém consegue mostrar um exemplo de como passar por todos os nós de uma árvore (grafo conexo não direcionado sem ciclos) e voltar ao nó inicial sem passar exatamente duas vezes por cada aresta?
Todos os casos de teste que eu desenhei acabaram retornando 2*A.
Ou estou considerando coisas demais? Se ele não pode tirar a caneta do papel o grafo é conexo. Se não tem ciclos, é uma árvore. Não pode aparecer (u,v) e (v,u), pois no input só aparecem arestas únicas.
Jefe replied 8 years ago
Sua abordagem esta correta, eu usei busca em profundidade, mas isso não deveria mudar a resposta, teste seu algoritmo para casos de teste de borda, e revise a parte do código onde você zera suas variáveis e estruturas, revise também o tamanho das suas estruturas.
Jean Costa replied 8 years ago
Não to conseguindo chegar a uma resposta correta. Minha ideia é a seguinte: primeiro eu faço um percurso em largura para saber o número de arestas existentes partindo do vértice de origem fornecido pela entrada, depois eu multiplico por dois o número de arestas, já que o percurso é de ida e volta. Se alguém puder me ajudar eu agradeço!