Дискретка_МетодПрима

#include <fstream>
#include <iostream>
#include <locale>





using namespace std;

int n; //Кол-во вершин
int treeline = 0; //Длина дерева
ifstream f("input.txt", ios::in);

//Построенние минимального остовного дерева методом Прима

void Prim(int** massive,bool* used){
	int minlen = 500000;  //Абсолютно любое очень большое число
	int q, w; //Переменные для хранения информации двух соединяемых вершин
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			if (massive[i][j] < minlen &&  massive[i][j] > 0 && used[i] == true && used[j] == false){  //Поиск минимального расстояния
				minlen = massive[i][j];
				q = i;
				w = j;
			}
		}
	}
	cout << " Связали " << q+1 << " и " << w+1 << "  длина = " << treeline << " + " << minlen << endl;
	treeline += minlen;
	used[w] = true;
}

void print(int** massive){
	for (int i = 0; i < n; i++){
		for (int j = i; j < n; j++){
			if (massive[i][j] > 0){
				cout << i+1 << "-" << j+1 << "=" << massive[i][j] << "   ";
			}
		}
	}
}

void main(){
	setlocale(LC_ALL, "rus");
	f >> n;
	bool* used = new bool[n];  //Массив , хранящий информацию о принадлежности вершин к дереву
	int** massive = new int*[n]; //Массив матрицы расстояний
	for (int i = 0; i < n; i++){
		massive[i] = new int[n];
		used[i] = false;  // Обнуляем массив
		for (int j = 0; j < n; j++){
		string s;
		f >> s;
		if (s == "~") massive[i][j] = -1;  //Если ~ то считаем как отрицательное число (для расстояния такое невозможно)
		else massive[i][j] = atoi(s.c_str());  // atoi = перевод строки в int значение
		}
	}
	print(massive);
	cout << endl;
	cout << endl;
	used[0] = true; //Заносим первую вершину в дерево
	for (int i = 0; i < n - 1; i++){  // Кол-во необходимых присоединений для построения дерева = n-1
		Prim(massive, used);
	}
	cout << endl;
	cout << endl;
	cout << "Длина минимального остовного дерева = " << treeline << endl;;
	cout << endl;
}