Aktualnosci

Algorytm Floyda-Warshalla

---

Algorytm Floyda Warshalla wyznaczający najmniejszy koszt przejścia między każdą parą wierzchołków.

• Złożoność czasowa wynosi O(n³),
• złożoność pamięciowa wynosi O(n²),
• graf może posiadać krawędzie o ujemnych wagach, ale nie może posiadać ujemnych cykli,
• algorytm wykorzystuje technikę programowania dynamicznego.

Wyznacz najmniejsze koszty przejścia dla każdej pary wierzchołków.

Wejście

W pierwszym wierszu wprowadzamy dwie liczby naturalne V i E określające odpowiednio liczbę wierzchołków oraz liczbę połączeń w grafie. W kolejnych E wierszach po trzy liczby definiujące połączenie między wierzchołkiem o numerze a oraz wierzchołkiem o numerze b o wadze w, 0 < a ≠ b ≤ n, |w| < 100, graf nie posiada ujemnych cykli.

Wyjście

Pary wszystkich wierzchołków a i b oraz najmniejszy koszt przejść między nimi.

//algorytm.edu.pl
//algorytm Floyda Warshalla do wyznaczania najkrótszych ścieżek 
//między każdą parą wierzchołków grafu.
//Nie mogą występować ujemne cykle
#include<bits/stdc++.h>
using namespace std;
vector <vector <long long> > tab;

//wyznaczenie najkrótszych ścieżek między każdą parą wierzchoków w czasie V^3
void Floyd_Warshall()
{
	for(int i = 1;i<tab.size();i++)
		for(int j=1;j<tab.size();j++)
			for(int k=1;k<tab.size();k++)
				if(tab[j][k] > tab[j][i] + tab[i][k])
					tab[j][k] = tab[j][i] + tab[i][k];
}

int main()
{
	int V, E; //wierzchołki i krawędzie
	cin>>V>>E;
	
	tab.resize(V+1); //utworzenie V + 1 wierszy (chcemy mieć dostęp do wierza o indeksie V)
	for(int i=1;i<=V;i++) 
		tab[i].resize(V+1, INT_MAX); //utworzenie V + 1 elementów w każdym wierszu i ustawienie na 
		//"nieskończoność" czyli INT_MAX — największą wartość mieszczącą się w zmiennej typu int
	for(int i=1;i<=V;i++)
		tab[i][i] = 0; //odległość od i-tego wierzchołka do siebie samego jest równa 0
		
	//wczytanie krawędzi i ich wag
	int a, b, w;
	while(E--)
	{
		cin>>a>>b>>w; //krawęd a -> b o wadze w
		tab[a][b] = w;
	}
	//po wykonaniu tego algorytmu w komórce tab[i][j] przechowujemy 
	//najmniejszy koszt przejścia z wierzchołka i do wierzchołka j
	Floyd_Warshall(); 
	//wypisujemy wyznaczone koszty
	for(int i = 1; i<= V; i++)
		for(int j = 1; j<=V; j++)
			if(tab[i][j] == INT_MAX)
				cout<<"brak połączenia\n";
			else
				cout<<i<<" -> "<<j<<": "<<tab[i][j]<<endl;
	return 0;
}

Przykład:

Wejście:

3 3
1 2 2
2 3 4
3 1 2

Wyjście:

1 -> 1: 0
1 -> 2: 2
1 -> 3: 6
2 -> 1: 6
2 -> 2: 0
2 -> 3: 4
3 -> 1: 2
3 -> 2: 4
3 -> 3: 0

vector::clear

---

Zasada działania

Metoda clear() czyści zawartość wektora. Po jej użyciu, w wektorze nie będzie znajdować się żadna wartość.

Przykład

Zadanie. Wpisz do wektora 5 znaków, wpisz liczbę elementów wektora, następnie wyczyść jego zawartość i ponownie wypisz liczbę znaków w wektorze.

Rozwiązanie

//algorytm.edu.pl
#include<iostream>
#include<vector>
using namespace std;

int main()
{
	char znak;
	vector <char> znaki;
	cout<<"Podaj 5 znaków: ";
	for(int i=0; i<5; i++) //np: abcde
	{
		cin>>znak;
		znaki.push_back(znak);
	}
	//wypisanie liczby elementów w wektorze
	cout<<"W wektorze znajduje się "<<znaki.size()<<" elementów.\n"; //W wektorze znajduje się 5 elementów.
	//czyszczenie zawartości wektora
	znaki.clear();
	cout<<"W wektorze znajduje się "<<znaki.size()<<" elementów."; //W wektorze znajduje się 0 elementów.
	return 0;
}

Deadline24 - 10 edycja

---

Trwa rejestracja na 10. edycję międzynarodowego maratonu programistycznego Deadline24

 

W dniach 7-8 kwietnia 2018 roku odbędzie się finał 10. — jubileuszowej — edycji międzynarodowego maratonu programistycznego Deadline24. Już teraz entuzjaści algorytmiki z całego świata mogą rejestrować się na eliminacje online, których wyniki zdecydują o tym, kto weźmie udział w wielkim finale.

Czytaj wiecej

XXIX runda Algoligi

---

XXIX runda konkursu programistycznego "Algoliga"

Już w najbliższą sobotę, 27 sierpnia, o godzinie 12:00 rozpocznie się 29 runda AlgoLigi. Konkurs potrwa do niedzieli do godziny 20:00.

Maciej Boniecki z Adamem Bąkiem dołożyli wszelkich starań, aby w przygotowanym przez nich zbiorze zadań każdy znalazł coś dla siebie niezależnie od poziomu. Możemy uchylić rąbka tajemnicy, że większość zadań została przez nas sklasyfikowana jako średnie, dlatego też gorąco zachęcamy jak największą liczbę zawodników do spróbowania swoich sił. Do zobaczenia w sobotę!

VIII Mistrzostwa WWSI w Programowaniu

---

Witamy!

Już po raz ósmy Koło Naukowe Miłośników Algorytmów ma zaszczyt zaprosić wszystkich chętnych do udziału w Mistrzostwach Warszawskiej Wyższej Szkoły Informatyki w Programowaniu. Po raz pierwszy w historii konkurs jest otwarty dla wszystkich użytkowników systemu SPOJ, a nie tylko dla studentów WWSI oraz uczniów biorących udział w programie IT Szkoła.

Zawody, jak co roku, składają się z dwóch rund. Najlepsi zawodnicy rundy pierwszej awansują do rundy finałowej. Zbiór zadań jest tak dopasowany, żeby każdy mógł znaleźć w nim coś dla siebie, nawet osoby bardzo początkujące. Więcej informacji odnośnie konkursu można znaleźć w regulaminie.

Rozpoczęcie zawodów już 5 marca o godzinie 12:00. Nie zwlekaj i zarejestruj się już dziś!

Zadania zostaną udostępnione na stronie konkursu w systemie SPOJ (dostępna tylko dla zarejestrowanych zawodników).