# PBinfo #590 – Prim – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
Se dă un graf neorientat ponderat conex cu n vârfuri și m muchii – în care fiecare muchie are asociat un cost, număr natural strict pozitiv. Folosind algoritmul lui Prim, determinați un arbore parțial de cost minim, cu rădăcina în vârful 1.

Date de intrare
Fișierul de intrare prim.in conține pe prima linie numerele n m, iar următoarele linii câte un triplet i j c, cu semnificația: există muchia (i j) și are costul c.

Date de ieșire
Fișierul de ieșire prim.out va conține pe prima linie costul arborelui de cost minim determinat, iar pe a doua linie vectorul de tați al arborelui, cu elementele separate prin exact un spațiu.

Restricții și precizări

1 ≤ n ≤ 100
costul unei muchii va fi mai mic decât 1000

Exemplu:
prim.in

7 11
1 2 2
1 7 4
2 3 3
2 5 2
2 6 3
2 7 3
3 4 1
3 5 2
4 5 1
5 6 3
6 7 5
prim.out

12
0 1 4 5 2 2 2

## Cod sursă C++

```cpp
#include <iostream>
#include <fstream>
#define INFINIT 1000000000
using namespace std;
ifstream fin("prim.in");
ofstream fout("prim.out");
int n , a[105][105], v[105], d[105], t[105];
int main()
{
    int i , j , c , m;
    fin >> n >> m;
    for(i =1 ; i <= n ; ++i){
		for(j = 1 ; j <= n ; ++j)
			a[i][j] = INFINIT;
		a[i][i] = 0;
	}
    while( m )
    {
		fin >> i >> j >> c;
    	a[j][i] = a[i][j] = c;
    	m --;
	}
	for(i =1 ; i <= n ; i ++ )
	{
		v[i] = 0;
		d[i] = a[1][i];
		t[i] = 1;
	}
	v[1] = 1; // vectorul de vizitati
	t[1] = 0; //vectorul de tati
	d[1] = 0; // vectorul cu costurile 
	d[0] = INFINIT;
	for(int k = 1 ; k < n ; ++k)
	{
		int pmax = 0;
		// alegem un varful nevizitat care se leaga de arborele curent cu cost minim
		for(i = 1 ; i <= n ; ++i)
			if(v[i] == 0 && d[i] < d[pmax])
				pmax = i;
		if(pmax > -1)
		{
			v[pmax] = 1;
			// verificam daca varful adaugat in arbore nu imbunatateste costurile de legare la arbore a varfurilor inca nevizitate
			for(i = 1; i <= n ; ++i)
				if(v[i] == 0 && d[i] > a[pmax][i])
					d[i] = a[pmax][i], t[i] = pmax;
		}
	}
	int S = 0;
	for(i = 1 ; i <= n ; ++i)
		S += d[i];	
	fout << S << endl;
	for(i = 1 ; i <= n ; ++i)
		fout << t[i] << " ";
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/590)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/590/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-590/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)