kolo

#include<algorithm>

#include<iostream>

using namespace std;

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

8int Find(int a)

9{

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

11}

12

13bool Union(int a, int b)

14{

15int fa = Find(a); 

16int fb = Find(b);18

 if (fa==fb) return 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 pair< int,pair<int,int> > krawedzie[300000]; 

34int main()

35{

36int n, m, a,b,c,koszt=0;

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

41for (int i=0; i<n; i++)

42{

43tab[i] = i; 

44ile[i] = 1; 

45}

46for (int i=0; i<m; i++)

47{

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

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

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

51}

52

53sort(krawedzie, krawedzie+m);

54cout<<endl;

55

56for (int i=0; i<m; i++)

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

58{

61}

62cout<<koszt;

63return 0;

64 }

1//algorytm Prima

2#include <iostream>

3#include <cstdlib>

5#define MX 10000 

7using namespace std;

9int main()

16int a, b, c; 

17int wiersz,wierzcholki,koszt;

18

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

20cin>>n>>m; 

22for(int i=1; i <= n; i++ ) 

23{

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

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

26for(int j=1; j <= n; j++ )

27{

29}

30}

31

32for (int i=1; i <= m; i++ ) //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=1; i<=n; i++) //przeszukanie pierwszego wiersza

50{

61 }

62

63koszt=MX; // maksymalny koszt

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

65{

76odwiedzone[wiersz]=1; // odwiedzony wierzcholek

77wierzcholki++; // przechodzimy do nstepnego wierzcholka

78}

79

80koszt=0; //koszty na poczatku rowne zero

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

82{

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

84}

85

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

88return 0;

89}