Najnowsze Wpisy

kruskala Komentarze (1)
04. czerwca 2016 10:46:00
linkologia.pl spis.pl

#include<algorithm>

#include<iostream>

using namespace std;

6int tab[100], ile[100];

8int Find(int a)

9{

10return (tab[a]==a) ? : (tab[a] = Find(tab[a]));

11}

12

13bool Union(int aint b)

14{

15int fa Find(a); 

16int fb Find(b);18

 

 if (fa==fbreturn false;

19if (ile[fa] <= ile[fb])

20{

21ile[fb] += ile[fa];

22tab[fa] = fb;

23}

24else

25{

26ile[fa] += ile[fb];

27tab[fb] = fa;

28}

29return true;

30}

31

32 pairint,pair<int,int> > krawedzie[300000]; 

34int main()

35{

36int nma,b,c,koszt=0;

38cout<<"Podaj liczbe wierzcholkow i krawedzi"<<endl;

39

cin>>n>>m;

40

 

41for (int i=0i<ni++)

42{

43tab[i] = i

44ile[i] = 1

45}

46for (int i=0i<mi++)

47{

48cout<<"Podaj wierzcholki krawedzi i jej wage"<<endl;

49cin>>a>>b>>c;

50krawedzie[i] = make_paircmake_pair(a,b) );

51}

52

53sort(krawedziekrawedzie+m);

54cout<<endl;

55

56for (int i=0i<mi++)

57if(Union(krawedzie[i].second.first,krawedzie[i].second.second))

58{

59

cout<<krawedzie[i].second.first<<" - "<<krawedzie[i].second.second<<" : "

<<krawedzie[i].first<<endl;

60

koszt += krawedzie[i].first//koszt (c)

61}

62cout<<koszt;

63return 0;

64 }

malukry122 : :

prima Komentarze (0)
04. czerwca 2016 10:42:00
linkologia.pl spis.pl

1//algorytm Prima

2#include <iostream>

3#include <cstdlib>

5#define MX 10000 

7using namespace std;

9int main()

10

{

 

 

 

11

int graf[100][100];

 

12

int odwiedzone[MX];

 

 

13

int waga[MX];

 

 

14

 

 

 

 

15

int m;

     

16int abc

17int wiersz,wierzcholki,koszt;

18

19cout<<"Podaj liczbe wierzcholkow i krawedzi"<<endl;

20cin>>n>>m

22for(int i=1<= ni++ ) 

23{

24odwiedzone[i]=0//nie ma poprzednikow i nastepnikow

25waga[i]=MX// waga jest rowna max

26for(int j=1<= nj++ )

27{

28

graf[i][j]=0// wypelnianie tablicy zerami

29}

30}

31

32for (int i=1<= mi++ ) //pobieranie drog w grafie

33{

34cout<<"Podaj wierzcholki krawedzi i jej wage"<<endl;

35cin>>a>>b>>c//droga miedzy a i b o wadze c

36graf[a][b]=graf[b][a]=c//wypelnianie tablicy danymi uzytkownika

37}

38

39// inicjalizacja danych do algorytmu Prima

40wiersz=1//zaczynamy od pierwszego wiersza, czyli przeszukujemy wszystkie polaczenia pierwszego wierzcholka

41waga[wiersz]=0// pierwsza waga rowna jest zero

42wierzcholki=1//zaczynamy od pierwszech wierzcholka

43odwiedzone[wiersz]=1// pierwszy wierzcholek odwiedzilismy, bo zaczynamy od

niego

45cout<<"Minimalne drzewo rozpinajace"<<endl;

46//algorytm Prima

47while(wierzcholki!=n// n liczba wierzcholkow

48{

49for(int i=1i<=ni++) //przeszukanie pierwszego wiersza

50{

51

if(graf[wiersz][i]!=0)//jezeli nie ma polaczenia z wierzcholkien to nie

wchodz

 

52

{

53

if(odwiedzone[i]==0)// jezeli byl odiweczony to nie wchodz

54

{

55

if(waga[i]>graf[wiersz][i])// jezeli jest droga o mniejszym

koszcie to nie wchodz

56

{

57

waga[i]=graf[wiersz][i]; // znaleziono najtansza droge,

podmiana za wczesniejsza

58

}

59

}

60

}

61 }

62

63koszt=MX// maksymalny koszt

64for(int i=1i<=ni++) // zanotowanie wagi w tabilcy

65{

66

if(odwiedzone[i]==0// sprawdzenie czy byl odwiedzony

67

{

68

if(waga[i]<koszt// sprawdzenie czy waga jest nizsza od maxa

69

{

70

koszt=waga[i]; // ustawienie nowej wagi jako koszt

71

wiersz=i// ustawienie wiersza w ktorym zmienilem wage

72

}

73

}

74

}

75

 

76odwiedzone[wiersz]=1// odwiedzony wierzcholek

77wierzcholki++; // przechodzimy do nstepnego wierzcholka

78}

79

80koszt=0//koszty na poczatku rowne zero

81for(int i=1i<=ni++) // dodaje wagi

82{

83koszt+=waga[i]; //suma wag

84}

85

86 cout<<"koszt = "<<koszt<<endl//wypisanie an ekran 87

88return 0;

89}

malukry122 : :

Archiwum

Kalendarz

pn wt sr cz pt so nd
303112345
6789101112
13141516171819
20212223242526
27282930123

Ksiega gości

Księga gości

Kategorie postow

Brak kategorii

remedium | aniolecek1989 | celi90 | bkitna-laguna | dunajka | Mailing