Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- //Функция конвертации матрицы смежности в список инцидентности
- vector < pair < int, pair<int,int> > > ArrayConvToList(int **arr, int n)
- {
- vector < pair < int, pair<int,int> > > res;// результирующий вектор
- for (int i = 0; i<n; i++)
- for (int j = 0; j<n; j++)
- if(arr[i][j]!=0)// если ребро существует
- res.push_back(make_pair < int, pair<int,int> >(arr[i][j],make_pair<int,int>(i,j)));
- return res;//вернем список
- }
- // главна функция
- int main()
- {
- //открываем файл для чтения
- ifstream in ("in.txt");//матрица смежности
- int n;// размерность
- in>>n;// читаем размер
- //выделяем память
- int **g = new int *[n];//под строку
- for (int i =0; i<n; i++)g[i] = new int [n];//под столбцы
- //читаем матрицу смежности
- for (int i = 0; i<n; i++)
- for (int j = 0; j<n; j++)
- in>>g[i][j];
- //преобразуем матрицу смежности в список инцидентности G = (V,E)
- vector < pair < int, pair<int,int> > > gl = ArrayConvToList(g,n); // вес - вершина 1 - вершина 2
- //сортируем вектор
- sort (gl.begin(), gl.end());
- // инвертируем , т.к. нам надо найти максимальный остов
- reverse(gl.begin(), gl.end());
- //Принадлежность вершины тому или иному поддереву хранится в массиве
- //belonging - в нём для каждой вершины хранится номер дерева, которому она принадлежит.
- vector<int> belonging (n);
- //инициализация массива разными значениями
- for (int i=0; i<n; ++i) belonging[i] = i;
- vector < pair<int,int> > tree ;// максимальный остов
- int tw = 0;//total weight - общий вес
- for (int i=0; i<gl.size(); ++i)// идем по списку ребер
- if (belonging[gl[i].second.first] != belonging[gl[i].second.second])//если концы не пренадлежат разным деревьям
- {
- tw += gl[i].first;//увеличиваем общий вес дерева
- tree.push_back (make_pair (gl[i].second.first, gl[i].second.second));//добавляем ребро в результат
- int left = belonging[gl[i].second.second],
- right = belonging[gl[i].second.first];
- // объедением два дерева
- for (int j=0; j<n; ++j)
- if (belonging[j] == left)
- belonging[j] = right;
- }
- //выводим результат
- reverse(tree.begin(), tree.end());
- cout<<"Max tree:"<<endl;
- for (int i=0; i<tree.size(); ++i)
- cout<<tree.at(i).second+1<<" - "<<tree.at(i).first+1<<"\tW("<<g[tree.at(i).first][tree.at(i).second]<<")."<<endl;
- cout<<"total weight:\t"<<tw<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement