Salutari tuturor,
Am tot cautat pe internet zilele astea pe infoarena,topcoder,codeforces si aparent nu pot gasi nimic despre aceasta problema:
Problema asta a aparut in destul de multe concursuri (o varianta destul de apropiata, chiar si la ICPC nwerc 2013).
Detaliile problemei:
Dandu-se matricea de drumuri minime al unui graf orientat, sa se gaseasca un graf care sa satisfaca matricea respectiva. Graful nu contine self-loops sau multi-edges. Daca nu se poate sa se afiseze -1, in caz contrar sa se afiseze matricea de adiacenta a grafului.
(restrictiile de care sunt interesat sunt n<=300, desi am vazut o varianta a problemei cu n mult mai mare)
Ex:
INPUT:
3
0 1 2
1 0 3
2 3 0
OUTPUT:
0 1 2
1 0 4
2 5 0
Din cate m-am gandit eu, ar trebui sa incerc sa fac un minimum spanning tree, pentru ca edge-urile respective garantat vor fi in graf, insa cum merg mai departe ? (nu sunt 100% sigur daca este corect ce am spus mai sus)
Multumesc si mult respect
!