#include <iostream> #include <vector> #include <limits> #include <algorithm> #define BIG // #define TEST using namespace std; #ifdef BIG const int matrixSize = 19; #else const int matrixSize = 8; #endif const std::string titles[matrixSize] = { "Langasovo", "Egorshino", "Orehovo", "Perm", "Voynovka", "Inskaya", "Omsk", "Ekaterinburg" #ifdef BIG , "Berdyaush", "Smichka", "Chusovskaya", "Agriz", "NNov", "Yudino", "Chelyabinsk", "Bogdanovich", "KUral", "Kurgan", "Altaiskaya" #endif }; typedef std::pair<int, int> Rec; //���� ��� ��������� ������� , i-j, ��� ������� � ���? /* ���� ��� ������� ����� ������ pair<int, int>, ��� � ������ ���� typedef ������ ������� �������� �������� �������, ������ - �� ���. */ class MyCluster { friend std::ostream& operator << (std::ostream&, MyCluster&); // �������� ������ �������� std::string get_vertexes(); void print(ostream& os) { os << "Vertexes: " << get_vertexes() << endl; os << "SREZ = " << sr << endl; os << "Edges:" << endl; for(unsigned i = 0; i < Edges.size(); i++) { os << "(" << Edges[i].first << " " << Edges[i].second << ")" << endl; } } vector<int> vx; // ������ ������, ������? /* ��, ��� ������ ������, ������� �� ������ ������ ����������� ����� �������� (����� � ���, ��������� ��, ������ ��� ��� ������ - ���� �� ����������) */ public: int sr; // �� �������. /* ��� ������? �� ��� ������ ������ �����, �������� SREZ = ... ? ��� ��� �� � ����. �� �� ������ ���-�� ��������� */ bool disabled; // �������� �� �������� ��� ����������� vector<Rec> Edges; // ����� MyCluster(int vertex): sr(0), disabled(false) { vx.push_back(vertex); // ��� �������� �������,���������� � ���� /* �� ������. ���-����, ��� �������� �������� �� �������, ��� ������� "��������" ���� */ } void updateEdge(Rec); void addEdge(Rec where) { Edges.push_back(where); // ��������� ����� } void operator += (MyCluster&); }; // friend functions std::ostream& operator << (std::ostream& os, MyCluster& cluster) // ������� ��� ������� { cluster.print(os); return os; } class EdgeUpdate { // ����� �������� ��� ����� public: Rec myPair; // �������� �� ������ /* ��� �� �����, ��� ������ ������������� ���������� ��� ���� ��� �������� ���� ��������. ���������� - ���� */ EdgeUpdate(const Rec &value): myPair(value) { } void operator() (Rec& edge) const {//��� ����� ���������� if(edge.first == myPair.first) edge.first = myPair.second; // �����? ����� ������ �� ���� �����.. /* ����� - � ������� �� ������, � ��������� �13: "������ �������� �� ���� ���������, � ���� ���-�� ���� ������ �� "������", �� ������ �� �� ������ �� "�����������", � ������� �������..." ���� ����� �� �������, �� �����-�� ������� ��� ������� ����� ��������� �� �������������� ���, � ����� �� ����� �������. ���������� �����: ��� ������������� ������ � myPair ������������ value, ���������� ��� �� MyCluster::updateEdge (� ������, �� ������ Updator, � ��� ��� ���� ��������? ��� ��� ��������? � �������� ��� ���� ��������, (jj, ii), �� ����, myPair.second-��� ������ �������������� ��������, � myPair.first - ������ ����, ������� ���-��� ����� �����������. ������� ���� ������ ������ �� ���� ��������� �������� ���������, � ������ �� ����������� �������� �� myPair.second, ���� ���������� ��� "�������", ��� � �������� � ���� ������). */ } }; void MyCluster::updateEdge(Rec myPair) { for_each(Edges.begin(), Edges.end(), EdgeUpdate(myPair)); // �������� ��� ���� ������� .. //��� ����?? /* � �������, ���� � ������� �� ���� ������? */ } std::string MyCluster::get_vertexes() // ������ ����� ������ { std::string res = ""; for(unsigned i = 0; i < vx.size(); i++) { res += titles[vx[i]] + " "; } return res; } struct Xists: public binary_function<int, vector<int>, bool> // �������..:) /* ������ ����������, � ������ ������� �� �����, Boost �� ����������� :) */ { bool operator() (const int& value, vector<int> vec) const { vector<int>::const_iterator it = std::find(vec.begin(), vec.end(), value);//���� � ������� �������? return (it != vec.end()) ? true : false;//true - ���� �����, false -���� ���. /* ���, ��� ������ ������� exists, ������� ����������, ���������� �� ������� � vector-� � ��������� ��� ���� �� �������� � ���������, �� � "�������" �� ������� */ } }; struct finder: std::binary_function< Rec, vector<int>, bool > { bool operator() (Rec const& in, vector<int> vec) const { return Xists()(in.first, vec); // ���� ��� ������ ���������� ������� � �������? /* ���... ��� ����������, ���������� �� � ������� ������ ������� ����, ����������� �����. �� ����, ���������� �� � ������� ������� ����� (��� ��� ���� ����� �� �������). ��������� ����? :) ��� ����������� ����, ����� ������� �� ������ ����� ��, ������� ��� "������" ��������, � �� ������� �� ���� ������... */ } }; void MyCluster :: operator += (MyCluster& cL) // �� ��� ������ QSet.intersect, ������ ��� ������� ? { // 0 ��������� ��������������� �������� �� cL.vx � this->vx remove_copy_if(cL.vx.begin(), cL.vx.end(), back_inserter(vx), bind2nd(Xists(), vx)); // 1 ��������� cL.Edges � ����� Edges copy(cL.Edges.begin(), cL.Edges.end(), back_inserter(Edges)); // 2 ������� ��� �� �������� �� Edges, ������� ������������� // �������, ����������� � finder Edges.erase(remove_if(Edges.begin(), Edges.end(), bind2nd(finder(), vx)), Edges.end()); } class Updator {//�������� �����? private: Rec myPair; public: Updator(const Rec& value) : myPair(value) { } void operator() (MyCluster& cluster) const { if(!cluster.disabled) {//���� ������� ������� cluster.updateEdge(myPair);//�������� ��� ����� "�����" ������. /* ����� �� ������ ���. � ��� ���� �������, ������ ���������� value, � ��� ��� ������. ��� ���, Updator ���������� ���������� for_each, �� ����, ��� ������� ��������� ����� ���������� updateEdge(). ��� �������� ��� - ��. ����. */ } } }; bool IsEnabled(const MyCluster& cluster) { return (cluster.disabled == false); // ��������� �� ���������� } int main() { int dm[matrixSize][matrixSize] = { #ifdef BIG { 0, 177, 171, 642, 981, 15, 403,1315, 689,1119, 311,1201, 420,1103, 595, 930, 89, 311,1020}, { 177, 0, 348, 465, 804, 192, 226,1138, 866, 942, 134,1024, 243, 926, 772, 753, 88, 134,1197}, { 171, 348, 0, 813,1152, 156, 574,1486, 518,1290, 482,1372, 591,1274, 424,1101, 260, 482, 849}, { 642, 465, 813, 0, 339, 657, 239, 673,1331, 477, 331, 559, 222, 461,1237, 288, 553, 331,1662}, { 981, 804,1152, 339, 0, 996, 578, 334,1670, 138, 670, 220, 561, 122,1576, 51, 892, 670,2001}, { 15, 192, 156, 657, 996, 0, 418,1330, 674,1134, 326,1216, 435,1118, 580, 945, 104, 326,1005}, { 403, 226, 574, 239, 578, 418, 0, 912,1092, 716, 92, 798, 17, 700, 998, 527, 314, 92,1423}, {1315,1138,1486, 673, 334,1330, 912, 0,2004, 196,1004, 114, 895, 212,1910, 385,1226,1004,2335}, { 689, 866, 518,1331,1670, 674,1092,2004, 0,1808,1000,1890,1109,1792, 94,1619, 778,1000, 331}, {1119, 942,1290, 477, 138,1134, 716, 196,1808, 0, 808, 82, 699, 16,1714, 189,1030, 808,2139}, { 311, 134, 482, 331, 670, 326, 92,1004,1000, 808, 0, 890, 109, 792, 906, 619, 222, 0,1331}, {1201,1024,1372, 559, 220,1216, 798, 114,1890, 82, 890, 0, 781, 98,1796, 271,1112, 890,2221}, { 420, 243, 591, 222, 561, 435, 17, 895,1109, 699, 109, 781, 0, 683,1015, 510, 331, 109,1440}, {1103, 926,1274, 461, 122,1118, 700, 212,1792, 16, 792, 98, 683, 0,1698, 173,1014, 792,2123}, { 595, 772, 424,1237,1576, 580, 998,1910, 94,1714, 906,1796,1015,1698, 0,1525, 684, 906, 425}, { 930, 753,1101, 288, 51, 945, 527, 385,1619, 189, 619, 271, 510, 173,1525, 0, 841, 619,1950}, { 89, 88, 260, 553, 892, 104, 314,1226, 778,1030, 222,1112, 331,1014, 684, 841, 0, 222,1109}, { 311, 134, 482, 331, 670, 326, 92,1004,1000, 808, 0, 890, 109, 792, 906, 619, 222, 0,1331}, {1020,1197, 849,1662,2001,1005,1423,2335, 331,2139,1331,2221,1440,2123, 425,1950,1109,1331, 0} #else { 0, 177, 171, 642, 981, 15, 403, 1315 }, { 177, 0, 348, 465, 804, 192, 226, 1138 }, { 171, 348, 0, 813, 1152, 156, 574, 1486 }, { 642, 465, 813, 0, 339, 657, 239, 673 }, { 981, 804, 1152, 339, 0, 996, 578, 334 }, { 15, 192, 156, 657, 996, 0, 418, 1330 }, { 403, 226, 574, 239, 578, 418, 0, 912 }, { 1315, 1138, 1486, 673, 334, 1330, 912, 0 } #endif }; // ������� ��������� ����� int sm[matrixSize][matrixSize];//������� ��� int used[matrixSize];//�������������� ������� int count=0; int min; for (int i=0; i< matrixSize; ++i)//�������� �����. { used[i]=0; for(int j=0;j< matrixSize;++j) sm[i][j]=0; } used[0]=1; int idx; do { min=std::numeric_limits<int>::max(); for(int i=0;i<matrixSize;++i) { if (used[i]!=0) { for(int j=0;j<matrixSize;++j) if ( (dm[j][i] < min) && (dm[j][i]!=0) && (used[j]==0)) { min=dm[j][i]; idx = j; } } } for(int i=0;i < matrixSize;++i) for(int j=0;j<matrixSize;++j) if( (dm[j][i]== min) && (used[j]==0) &&(used[i]==1)) { used[j] =1; sm[j][i]= sm[i][j] = min; count++; i=matrixSize; break; } } while(count < matrixSize-1); // ������� ������� ��� ... for(int i = 0; i < matrixSize; i++) { for(int j = 0; j < matrixSize; j++) { std::cout << sm[i][j] << " "; } std::cout << std::endl; } /* **** */ vector<MyCluster> clusters; // ������ ���������/������ for(int i = 0; i < matrixSize; i++) { clusters.push_back(MyCluster(i)); // ������� �������� /* �������-�� �� ��� ��� ��������, ���������� ����� �� ����� �������, �� ���� ���� ���-���� ������� �� ������� ��������� - �� ����� ����� ��� :) */ } vector<MyCluster> res; // ? /* � ��� ������ ���������, � � �� ������ � �� ����� ������� �������� ������ �����, ��� ���� ���-�� ������� ����������? �� ��������� ����� do { ... } while(counter > 1) ���������� � ������� clusters ��� ������������ (��� ��������� ������ ��� �������� ���������, ��� ������ ������� ����������� - �� �� �������������� ������) */ for(int i = 0; i < matrixSize; i++) for(int j = 0; j < matrixSize; j++) { if(sm[i][j] > 0) { clusters[i].addEdge(make_pair(j, sm[i][j]));//������� ����� } } int counter;//�������? /* ��, ��� ����� ������� �������� ��� ��������� */ do { int ii = -1, jj = -1;// ? /* � ���� ������� �������������� GCC, ��� "����� ���� �������������������� ��������" */ min = std::numeric_limits<int>::max();// for(int i = 0; i < matrixSize; i++)//���� ���. ������ { if(clusters[i].disabled) continue;//���� ������� �������������, ����������� ���� ��� for(unsigned j = 0; j < clusters[i].Edges.size(); j++) { if((clusters[i].Edges[j].second < min) && (clusters[clusters[i].Edges[j].first].disabled == false)) //���� ������� ������� � ��� �������� �����,..� ��� ������ � second ���?? <min, � //� ������� ��� �������� �������� �������� � ��� ������ ����� ������� /* ���� ��� �������� ����� � ������� �������� ������ min (�.�., ������� �� ���� ������ ��������), � ��� �������, �� ������� ��������� ��� �����, ������� (� ���� ����� ��� ��� �� ������), ��... */ { ii = i; jj = clusters[i].Edges[j].first; min = clusters[i].Edges[j].second; //����� (��� ii,jj - �� �������) ����� ����������� ����� � ��� ��� �������.. ? /* ... � ii ���������� ����� ��������, � ������� ��������� ������� �������, � jj - �������� ������� �������� ����� � ���� �������� (��� ��� � ��� ����������? ���������, ��� ����������, ��� ����� ����������� ����� ������� �� �������� ii � ������� jj), � ���������� ��������� ��� ������� */ } } } #ifdef TEST cout << "test: min = " << min << " ii = " << ii << " jj = " << jj << endl; cout << clusters[ii] << endl << clusters[jj] << endl; #endif clusters[ii] += clusters[jj]; // ��������� �������???? /* ������� ��������: clusters[ii] ��������� clusters[jj] */ clusters[ii].sr = min;//� ��� ��� ���� �� ������� /* � ����������, � ����� ������ ��� ��������� (��� ����� ����) */ //������ � ������� /* � ��� �������� �� ����... � ������� ���, ����, � EdgeUpdate ��� ����������... ��� ���: ��������� �� ���� ������, � ��� ������� �� ��� ��������� ��, ��� ������ Updator-��, � ������: ���� ������� �������, �� ��� ��� �����, ������� ��������� �� JJ ����� ������ ��������� �� II, ��� �� ����� �� ������� ���������� �������� JJ, � �� ������ ������������� �� �����, �� � ���� ������ ����������. */ for_each(clusters.begin(), clusters.end(), Updator(make_pair(jj, ii)));//��� ������ ��������/������� //� ������� ��������� �������� ��� ����� �� jj,ii �����������..�� ������� � �����. clusters[jj].disabled = true; // jj ������� ����� res.push_back(clusters[ii]); // � ������ ��������� ������� ii #ifdef TEST cout << "result = " << endl << clusters[ii]; cin.get(); #endif counter = count_if(clusters.begin(), clusters.end(), IsEnabled);//�������� ���������� �������� ������ #ifdef TEST cout << "Counter = " << counter << endl; #endif } while(counter > 1);//�� ��� ��, ���� ���������� �������� ������ ����� 1 std::cout << res.size() << std::endl; std::vector<MyCluster>::iterator it; for(it = res.begin(); it != res.end(); it++) { cout << *it << endl << endl << endl;//�� � �������, ������, ���� ��������... } return 0; }