h3. Probleme asemanatoare
* 'Problema celor $N$ regine [ clasica ] & co.':http://acm.fzu.edu.cn/reference/Search%20Techniques.htm

* 'Dame2 / Summer Challenge 2007':problema/dame2

h2. Rfinv

h3. Solutie de complexitate $O(N^4^)$
 
Vom sorta toate cele $O(N^2^)$ distante din matrice in ordine crescatoare si vom initializa o matrice $D[i][j]=infinit$, pentru $i <> j$, respectiv $0$, pentru $i=j$. Pe masura ce parcurgem sirul sortat al distantelor, vom actualiza valorile din matricea $D$. Sa presupunem ca am ajuns la o distanta avand valoarea $x$, ce reprezinta distanta minima dintre $2$ noduri $i$ si $j$. Daca $D[i][j] < x$ sau $D[i][j] > x$ si nu exista muchie in graf intre $i$ si $j$, atunci nu avem solutie si ne oprim. Daca $D[i][j] > x$ si exista muchie intre $i$ si $j$, atunci vom pune pe aceasta muchie costul $x$. In continuare, va trebui sa actualizam valorile $D[a][b]$ afectate de setarea valorii $x$ pe muchia $(i,j)$. Mai exact, pentru fiecare pereche de noduri $(a,b)$, $D[a][b]$ va fi egal cu minimul dintre valoarea actuala $D[a][b]$ si $min { D[a][i] + x + D[j][b], D[a][j] + x + D[i][b] }$.
 
Daca nu am intalnit nici o contradictie pe masura ce am parcurs muchiile, atunci raspunsul este $"DA"$ ; in caz contrar, raspunsul este $"NU"$.
 
h3. Solutie de complexitate $O(N^3^)$
 
Pe fiecare muchie a grafului $(i,j)$ se pune o distanta egala cu valoarea $A[i][j]$ ($A$ fiind matricea data). Se aplica apoi algoritmul 'Roy-Floyd':http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm pe acest graf, iar matricea distantelor obtinuta trebuie sa fie identica cu matricea distantelor data (in caz contrar neexistand solutie).
 
h3. Probleme asemanatoare
 
* 'rf / Happy Coding 2006':problema/rf
 

h2. Pali
h2. Furnica