Jak możnaby sprawdzić ww liczbę? O ile wiem mniejwięcej co z resztą (stopień min/max, liczba składowych spójności), to akurat na to, nie mam pomysłu :(.
podnieść macierz przyległości do 3 potęgi, zsumować wartości na głównej przekątnej i podzielić przez 6
Hm, nie bardzo Cię zrozumiałem, spróbowałem wykombinować coś po swojemu mając do dyspozycji macierz sąsiedztwa:
int trojakty(int **macierz, int size)
{
int wynik = 0;
for(int i = 0; i < size - 1; i++) //wiersze
{
//kolumny
for(int n = 0; n < size - 1; n++)
{
if(macierz[i][n] != 0 && macierz[i][n+1] != 0 && macierz[i+1][n+1] != 0) //jeżeli mam taką trójkę
{
wynik += (macierz[i][n] * macierz[i][n+1] * macierz[i+1][n+1]);
macierz[i][n] = 0; //zeruję pola jak i ich symetryczne odpowiedniki
macierz[n][i] = 0;
macierz[i][n+1] = 0;
macierz[n+1][i] = 0;
macierz[i+1][n+1] = 0;
macierz[n+1][i+1] = 0;
}
}
}
return wynik;
}
Jednak ten sposób nie działa (chyba?) do końca poprawnie, przechodzi tylko 2/6 testów (SPOJ - contest zamknięty, przykro mi). Jakieś dalsze wskazówki? Co pomijam w powyższym rozwiązaniu, jaki przypadek?
Twój algorytm nie rozumiem za bardzo...
macierz przyległości/sąsiedztwa zawiera liczbę tras długości jeden pomiędzy poszczególnymi wierzchołkami
po podniesieniu jej do trzeciej potęgi otrzymujemy w macierzy trasy długości 3
interesują nas trójkąty, czyli trasy zaczynające się i kończące w tym samym miejscu, więc sumujemy trasy z głównej przekątnej
każdy trójkąt został policzony w 3 wierzchołkach oraz przechodząc po nim w dwóch kierunkach, więc dzielimy na 6
ten opis zakłada, że graf jest nieskierowany i nie ma pętli, jeśli tak nie jest, trzeba go zmodyfikować odrobinę