infoarena informatica de performanta
info
arena
b
log
f
orum
calendar
autentificare
inregistrare
infoarena
>
infoarena - concursuri, probleme, evaluator, articole
>
Probleme externe
>
UVA
> Subiect:
10806 - Dijkstra, Dijkstra.
Pagini: [
1
]
În jos
« mesajul precedent
următorul mesaj »
Imprimă
Ajutor
Subiect: 10806 - Dijkstra, Dijkstra. (Citit de 12170 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
•
Dastas
Vorbaret
Karma: 11
Deconectat
Mesaje: 170
10806 - Dijkstra, Dijkstra.
«
:
Ianuarie 01, 2008, 18:52:00 »
http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=20&page=show_problem&problem=1747
Iau WA. Pe toate testele pe care le pot verifica manual (sau cu back; ar fi culmea ca si backu sa dea *acelasi* raspuns gresit) imi da bine. Aveti niste teste sau idei ce ar putea avea?
Eu gasesc un drum minim, fac niste transformari pe graf, mai gasesc un drum minim, iar apoi prelucrez drumurile gasite...
Memorat
•
pauldb
Nu mai tace
Karma: 821
Deconectat
Mesaje: 1.901
Răspuns: 10806 - Dijkstra, Dijkstra.
«
Răspunde #1 :
Ianuarie 01, 2008, 19:16:25 »
Pe urmatorul exemplu:
4 5
1 2 1
2 3 1
3 4 1
1 3 2
2 4 2
daca initial alegi drumul minim 1-2-3-4, iti mai merge rezolvarea?
Memorat
Am zis
•
Dastas
Vorbaret
Karma: 11
Deconectat
Mesaje: 170
Răspuns: 10806 - Dijkstra, Dijkstra.
«
Răspunde #2 :
Ianuarie 01, 2008, 19:23:25 »
Nu m-am uitat ce drum aleg (ar fi mai dificila reconstituirea..), dar imi da 6, atat cu rezolvarea eficienta cat si cu back. Nu e bine 6?
Memorat
•
pauldb
Nu mai tace
Karma: 821
Deconectat
Mesaje: 1.901
Răspuns: 10806 - Dijkstra, Dijkstra.
«
Răspunde #3 :
Ianuarie 01, 2008, 19:59:17 »
E bine 6. Problema e ce drum alegi initial. Daca alegi 1-2-4 sau 1-3-4 initial, la pasul 2 ii poti alege perechea. Daca alegi 1-2-3-4 initial, nu vei mai avea drum pentru pasul 2. Algoritmul de drum minim nu iti garanteaza ce drum alegi initial. Intamplator, pe testul pe care ti l-am dat il alegeai bine. Incearca si testul asta:
4 5
1 2 1
2 3 1
3 4 1
1 3 3
2 4 3
Trebuie sa dea 8.
Memorat
Am zis
•
Dastas
Vorbaret
Karma: 11
Deconectat
Mesaje: 170
Răspuns: 10806 - Dijkstra, Dijkstra.
«
Răspunde #4 :
Ianuarie 01, 2008, 20:21:45 »
Pai eu nu fac pur si simplu drum initial + eliminare muchii + inca un drum. Am zis ca fac unele modificari pe graf si pe acest drum. Pe exemplu imi da 8.
Cat despre algoritm, mai pe larg e cam asa:
Gaseste un drum minim de la 1 la n.
Toate muchiile le inlocuiesc cu arce orientate catre sursa (mai exact, daca drumul e format din muchiile (1,2), (2,3), acestea vor fi inlocuite cu arcele 2->1 si 3->2). Costul acestor arce il pun pe -1.
Rulez din nou algoritmul de drum minim (eu am ales bellman ford sa n-am probleme cu costurile negative..). Apoi elimin muchiile alese atat in primul drum cat si in cel de-al doilea, si imi raman muchiile drumului dus-intors.
Edit: Alte idei de rezolvare care ar fi? Am inteles ca se poate face si cu flux?
«
Ultima modificare: Ianuarie 01, 2008, 20:59:12 de către Ionescu Vlad
»
Memorat
•
pauldb
Nu mai tace
Karma: 821
Deconectat
Mesaje: 1.901
Răspuns: 10806 - Dijkstra, Dijkstra.
«
Răspunde #5 :
Ianuarie 01, 2008, 21:45:13 »
Contraexemplu:
4
6
1 2 4
2 3 4
3 4 4
1 3 9
2 4 9
1 4 16
Tie iti da 28, raspunsul este 26.
Problema se rezolva cu flux. Tu faci ceva asemanator, mai putin ca arcele de intoarcere le faci -1 si nu -cost.
Memorat
Am zis
•
Dastas
Vorbaret
Karma: 11
Deconectat
Mesaje: 170
Răspuns: 10806 - Dijkstra, Dijkstra.
«
Răspunde #6 :
Ianuarie 01, 2008, 21:51:10 »
Nu m-as fi gandit la asta
. Mersi mult, am luat accepted.
Memorat
Pagini: [
1
]
În sus
Imprimă
infoarena
>
infoarena - concursuri, probleme, evaluator, articole
>
Probleme externe
>
UVA
> Subiect:
10806 - Dijkstra, Dijkstra.
« mesajul precedent
următorul mesaj »
Schimbă forumul:
Selectează o destinaţie:
-----------------------------
infoarena - concursuri, probleme, evaluator, articole
-----------------------------
=> Concursuri
===> Junior Challange 2023
===> Algoritmiada 2022
=====> Runda 1
=====> Runda 2
=====> Runda 3
=====> Runda 4
===> Summer Challenge 2021
===> Junior Challenge 2021
===> FMI No Stress 10
===> Winter Challenge 2020
===> Autumn WarmUp 2020
===> Summer Challenge 2020
===> Junior Challenge 2020
===> Concurs de incalzire 2020
===> FMI No Stress 9
===> Autumn WarmUp 2019
===> Summer Challenge 2019
===> Junior Challange 2019
===> Algoritmiada 2019
===> Info Oltenia 2019
===> Arhiva concursuri
=====> Info Oltenia 2018
=====> Junior Challenge 2018
=====> Algoritmiada 2018
=====> AGM 2018
=====> Grigore Moisil 2018
=====> RCPC 2018
=====> Fmi No Stress 8
=====> Urmasii lui Moisil 2017
=====> Grigore Moisil 2017
=====> Prosoft @ NT
=====> Algoritmiada 2017
=====> PreOJI 2017
=====> FMI No Stress 2017
=====> AGM 2017
=====> Lot 2017
=====> ACM ICPC Faza Nationala 2017
=====> PreOJI 2016
=====> ONIS 2016
=====> Grigore Moisil 2016
=====> Urmasii lui Moisil 2016
=====> AGM 2016
=====> Algoritmiada 2016
=====> FMI No Stress 6
=====> Urmasii lui Moisil 2015
=====> FMI No Stress 5
=====> ONIS 2015
=====> Concursul National de Soft Grigore Moisil Lugoj
=====> ACM-ICPC Faza Nationala 2014-2015
=====> Infoarena Monthly 2014
=====> Concurs Mihai Patrascu 2013
=====> Algoritmiada 2015
=====> AGM 2015
=====> Junior Challenge 2015
=====> ONIS 2014
=====> Algoritmiada 2014
=====> FMI No Stress 4
=====> preONI 2006
=====> .com 2012
=====> Infoarena Monthly 2012
=====> Code Pandas
=====> Algoritmiada 2013
=====> FMI No Stress 3
=====> FMI No Stress 2012
=====> Junior Challenge 2012
=====> Algoritmiada 2012
=====> .com 2011
=====> Girls Programming Camp 2011
=====> Algoritmiada 2011
=====> F11 Competition 2011
=====> Tiberiu Popoviciu 2011
=====> Grigore Moisil 2011
=====> RMMS 2011
=====> FMI No Stress 2010
=====> Grigore Moisil 2010
=====> .com 2009
=====> Stelele Informaticii 2009
=====> Stelele Informaticii 2010
=====> Algoritmiada 2009
=====> Algoritmiada 2010
=====> Grigore Moisil 2009
=====> CCEX 2009
=====> Summer Challenge 2009
=====> All You Can Code 2008
=====> Selectie echipe ACM ICPC, UPB 2008
=====> Junior Challenge 2008
=====> Happy Coding 2008
=====> preONI 2008
=====> Grigore Moisil 2008
=====> Winter Challenge 2008
=====> Happy Coding 2007
=====> Autumn Warmup 2007
=====> preONI 2007
=====> Summer Challenge 2007
=====> Junior Challenge
=====> Winter Challenge 1
=====> Unirea 2007
=====> Happy Coding 2006
=====> Autumn WarmUp 2006
=====> Summer Challenge Doi
=====> Summer Challenge
=====> Happy coding
=====> Grigore Moisil
=====> Happy Birthday Infoarena
===> RCPC 2019
===> Summer Challenge Trei
=> Arhiva de probleme
===> Probleme pentru bacalaureat
=> Arhiva Infoarena Monthly
=> Arhiva ACM
=> Arhiva educationala
=> Concursuri virtuale
=> Informatica
===> Teme
=> Articole
===> Downloads
=> Probleme externe
===> .CAMPION
===> SGU
===> TIMUS
===> UVA
===> SPOJ
===> PKU
===> TJU
-----------------------------
Comunitate - feedback, proiecte si distractie
-----------------------------
=> Implica-te!
===> Arhiva educationala
===> Imbunatatire teste
===> Development
===> Scrie articole
===> Extinde arhiva
=> Blog
=> Feedback infoarena
===> Sondaje
===> Arhiva
===> IAP (Infoarena Proposal)
=> Off topic
Se încarcă ...