#include <iostream> #include <vector> #include <algorithm> #include <ctime> #include <string> #include <cmath> using namespace std; #define fori(n) for(int i=0;i<n;i++) #define forj(n) for(int j=0;j<n;j++) int inf = 1000000000; string viv(int x){return x==inf?"oo":to_string(x);} int vich(int a, int b) {return a==inf||a==0?a:a-b;} int sum(vector<vector<int>> matr, vector<int> masi, vector<int> masj, int i1, int j1, int n) { int slog1, slog2; int minim=inf; forj(n) if(matr[i1][masj[j]]<minim && masj[j]!=j1) minim=matr[i1][masj[j]]; slog1=minim; minim=inf; fori(n) if(matr[masi[i]][j1]<minim && masi[i]!=i1) minim=matr[masi[i]][j1]; slog2=minim; return slog1+slog2; } void viv(vector<vector<int>> matr, vector<int> masi, vector<int> masj, int n) { cout << " \t"; fori(n) cout << masj[i]+1 << "\t"; cout << endl; fori(n) { cout << masi[i]+1 << "\t"; forj(n) cout << viv(matr[masi[i]][masj[j]]) << "\t"; cout << endl; } } void vivi(vector<int> i, char a) { int sum=0; cout << a << "i : "; for(auto x: i) { cout << x << " "; sum+=x; } cout << "summa=" << sum << endl; } void vivz(vector<int> Z, string q) { cout << q << "= ("; for(auto x: Z) cout << x << " "; cout << ")\n"; } void vivpyt(vector<pair<int,int>> pyt) { fori(pyt.size()-1) cout << pyt[i].first+1 << " " << pyt[i].second+1 << " >> "; cout << pyt.back().first+1 << " " << pyt.back().second+1; } void vivmatr(vector<vector<int>> matr) { cout << "\n \t"; fori(matr.size()) cout << i+1 << "\t"; cout << "\n"; fori(matr.size()) { cout << i+1 << "\t"; forj(matr.size()) cout << viv(matr[i][j]) << "\t"; cout << endl; } } void showpyt(vector<pair<int,int>> pyt) { int tmp=0; for(int i=0;i<pyt.size();i++) { for(int j=0;j<pyt.size();j++) { if(pyt[j].first==tmp) { tmp=pyt[j].second; swap(pyt[j], pyt[i]); break; } } } fori(pyt.size()-1) cout << pyt[i].first+1 << " "; cout << pyt[pyt.size()-1].first+1; } void showvetvlen(vector<pair<int,int>> &vetvlenie) { fori(vetvlenie.size()-1) cout << "(" << vetvlenie[i].first+1 << ", " << vetvlenie[i].second+1 << "), "; cout << "(" << vetvlenie[vetvlenie.size()-1].first+1 << ", " << vetvlenie[vetvlenie.size()-1].second+1 << ")"; } ////////////////////////////////////////////////////////////////////////////// void showtreepyt(vector<pair<int,int>> pyt, pair<int,int> vetvlenie, vector<pair<int,int>> pytviv, int count) { //vivpyt(pyt); cout << " " << vetvlenie.first+1 << ", " << vetvlenie.second+1 << "\n"; static int i; if(count) { for(int j=0;j<i;j++) cout << " | "; } for(i=0;i<pyt.size();i++) if(pyt[i]==vetvlenie) { for(int j=0;j<i;j++) cout << " | "; cout << " "; vivpyt(pytviv); break; } } void treerecyr(vector<vector<pair<int,int>>> pyt2D, vector<int> dlini, vector<vector<pair<int,int>>> vetvlenie, int max, int l, int r, int count) { for(int i=r;i>=l;i--) { //cout << " >> " << i << " " << vetvlenie[i].size() << " << "; if(vetvlenie[i].size()==count&&count<=max) { showtreepyt(pyt2D[l],vetvlenie[i][count-1], pyt2D[i+1], count-1); cout << ".\tDlina=" << dlini[i+1] << endl; treerecyr(pyt2D, dlini, vetvlenie, max, i-1, r, count+1); r=i-1; } } } void showtree(vector<vector<pair<int,int>>> pyt2D, vector<int> dlini, vector<vector<pair<int,int>>> vetvlenie) { int max=0; vivpyt(pyt2D[0]); cout << ".\tDlina=" << dlini[0] << endl; fori(vetvlenie.size()) if(max<vetvlenie[i].size()) max=vetvlenie[i].size(); treerecyr(pyt2D, dlini, vetvlenie, max, 0, vetvlenie.size()-1, 1); } ////////////////////////////////////////////////////////////////////////////// int dlinapyt(vector<vector<int>> matr, vector<pair<int,int>> pyt) { int sumpyt=0; fori(pyt.size()) sumpyt+=matr[pyt[i].first][pyt[i].second]; return sumpyt; } void gamm(vector<vector<int>> &matr, vector<pair<int,int>> &pyt, int n, vector<int> masi, vector<int> masj, vector<int> &Z, vector<int> &Z_, int &h) { vector<int> ai; vector<int> bi; int minim; fori(n) { minim=inf; forj(n) if(matr[masi[i]][masj[j]]<minim) minim=matr[masi[i]][masj[j]]; h+=minim; ai.push_back(minim); forj(n) matr[masi[i]][masj[j]]=vich(matr[masi[i]][masj[j]], minim); } vivi(ai, 'a'); //viv(matr, masi, masj, n); fori(n) { minim=inf; forj(n) if(matr[masi[j]][masj[i]]<minim&&matr[masi[j]][masj[i]]!=inf) minim=matr[masi[j]][masj[i]]; h+=minim; bi.push_back(minim); forj(n) matr[masi[j]][masj[i]]=vich(matr[masi[j]][masj[i]], minim); } vivi(bi, 'b'); viv(matr, masi, masj, n); Z.push_back(h); int maxi, maxj, maxs=-1, summa; cout << "\nD= {"; fori(n) forj(n) if(matr[masi[i]][masj[j]]==0) { summa=sum(matr, masi, masj, masi[i], masj[j], n); cout << "(" << masi[i]+1 << ", " << masj[j]+1 << ") = " << summa << ", "; if(summa>maxs) { maxs=summa; maxi=masi[i]; maxj=masj[j]; } } cout << "}\nDyga vetvlenia: (" << maxi+1 << ", " << maxj+1 << "); h=" << h << "\n"; if(h+maxs<inf) { cout << "Nizhnaa granica=" << h+maxs << "\n"; Z_.push_back(h+maxs); } pyt.push_back(make_pair(maxi, maxj)); } void kon(vector<int> &mass, int n, int q) { for(int i=0;i<n-1;i++) if(mass[i]==q) swap(mass[i],mass[i+1]); } void pushinf(vector<vector<int>> &matr, vector<pair<int,int>> pyt, int n, vector<int> masi, vector<int> masj, int nn) { vector<int> flag(nn); vector<int> ekv(nn,-1); fori(pyt.size()) ekv[pyt[i].first]=pyt[i].second; int ekvp; for(int in=0;in<n;in++) { for(int i=0;i<flag.size();flag[i++]=0); ekvp=masi[in]; int ij; for(ij=0;ij<ekv.size();ij++) if(ekv[ij]==ekvp) { flag[ij]=1; ekvp=ij; ij=-1; } for(int i=0;i<nn;i++) if(flag[i]) matr[masi[in]][i]=inf; } } void pushinf1(vector<vector<int>> &matr, vector<pair<int,int>> pyt, int n, vector<int> masi, vector<int> masj, int nn) { vector<int> ekv(nn,-1); fori(pyt.size()) ekv[pyt[i].first]=pyt[i].second; int ekvp; for(int in=0;in<n;in++) { ekvp=masi[in]; int ij; for(ij=0;ij<ekv.size();ij++) if(ekv[ij]==ekvp) { matr[masi[in]][ij]=inf; ekvp=ij; ij=-1; } } } void vvodcin(vector<vector<int>> &matr, int n) { for(auto &i: matr) for(auto &x: i) cin >> x; fori(n) matr[i][i]=inf; } void vvodrand(vector<vector<int>> &matr, int n, int min, int max) { for(auto &i: matr) for(auto &x: i) x=rand()%(max-min)+min; fori(n) matr[i][i]=inf; vivmatr(matr); fori(n) cout << "---------"; cout << endl; } int min(vector<int> a) { int min=inf; for(auto x: a) if(x<min) min=x; return min; } bool ysvet(vector<int> Z_, int h) { fori(Z_.size()) if(h>Z_[i]) return true; return false; } int recyrs(vector<vector<int>> matr, int n, int h, pair<int,int> iskl, vector<vector<pair<int,int>>> &pyt2D, vector<int> &dlini, vector<vector<pair<int,int>>> &vetvlenie, vector<pair<int,int>> vetvlen) { if(iskl.first!=-1) matr[iskl.first][iskl.second]=inf; int htmp=0, n1; n1=n; vector<vector<int>> matr1; vector<int> masi(n); vector<int> masj(n); vector<int> Z_; vector<int> Z; vector<pair<int,int>> pyt; fori(n) {masi[i]=i; masj[i]=i;} matr1=matr; for(;n1>0;n1--) { cout << "\n"; viv(matr1, masi, masj, n1); if(n1>=2) pushinf1(matr1, pyt, n1, masi, masj, n); gamm(matr1, pyt, n1, masi, masj, Z, Z_, htmp); cout << "\n"; fori(n) cout << "========="; cout << "\n"; kon(masi, n1, pyt.back().first); kon(masj, n1, pyt.back().second); matr1[pyt.back().first][pyt.back().second]=inf; } vivz(Z, "Z"); vivz(Z_, "Z_"); vivpyt(pyt); pyt2D.push_back(pyt); dlini.push_back(htmp); if(htmp<h) h=htmp; cout << "\nDlina=" << h << " (" << htmp << ")" << ", (" << dlinapyt(matr, pyt) << ")\n"; fori(Z_.size()) if(Z_[i]<h) { iskl=pyt[i]; vetvlen.push_back(iskl); cout << "\n\n/////////////////////////////" << "\n------------Vetvlenie begin------------\n" << "Vetv " ; showvetvlen(vetvlen); vetvlenie.push_back(vetvlen); h=recyrs(matr, n, h, iskl, pyt2D, dlini, vetvlenie, vetvlen); cout << "\nVetv "; showvetvlen(vetvlen); cout << "\n------------Vetvltnie end------------\n"; vetvlen.pop_back(); } return h; } void alg(int n) { vector<vector<int>> matr(n, vector<int> (n)); vector<pair<int,int>> vetvlen; vector<vector<pair<int,int>>> pyt2D; vector<vector<pair<int,int>>> vetvlenie; vector<int> dlini; pair<int,int> iskl(-1, 0); int h=inf; //*/ vvodcin(matr, n); /*/ vvodrand(matr, n, 0, 50); //*/ h=recyrs(matr, n, h, iskl, pyt2D, dlini, vetvlenie, vetvlen); vivmatr(matr); cout << "Pyt " << 1 << ": "; vivpyt(pyt2D[0]); cout << ".\tDlina=" << dlini[0] << endl; //showpyt(pyt2D[0]); //cout << endl; fori(dlini.size()-1) { cout << "Pyt " << i+2 << ": "; vivpyt(pyt2D[i+1]); cout << ".\tDlina=" << dlinapyt(matr, pyt2D[i+1]) << " -> Vetvlenie po dyge "; showvetvlen(vetvlenie[i]); cout << "\n"; //showpyt(pyt2D[i+1]); //cout << endl; } cout << "Dlina=" << h << "\n"; cout << "\n\n\n"; //showtree(pyt2D, dlini, vetvlenie); } int main() { int n; srand(time(NULL)); cin >> n; if(n) { alg(n); cout << "\n////////////////////////////////////////////////////////////////" << "\n////////////////////////////////////////////////////////////////" << "\n////////////////////////////////////////////////////////////////" << "\n\n"; } system("pause"); return 0; } /* 5 10000 30 40 15 6 10 10000 18 7 9 20 30 1000 0 10 25 10 35 10000 5 9 8 7 6 10000 6 1000 11 12 16 22 14 22 100 18 18 6 15 22 10 100 19 6 18 8 15 14 100 18 22 13 19 15 18 100 14 10 8 16 23 5 1000 6 1000 10 12 5 22 18 11 1000 14 23 20 10 16 11 1000 6 21 24 5 21 6 1000 11 13 13 11 9 24 1000 22 16 7 17 12 24 1000 6 1000 8 6 7 15 19 22 1000 24 16 20 11 21 20 1000 5 24 12 14 23 7 1000 9 17 17 6 13 24 1000 13 23 8 20 12 14 1000 6 1000 14 10 20 9 10 10 1000 23 12 13 23 21 9 1000 19 15 11 19 12 10 1000 19 24 19 24 14 23 1000 11 21 22 12 21 9 1000 6 1000 10 12 5 22 18 11 1000 14 23 20 10 16 11 1000 6 21 24 5 21 6 1000 11 13 13 11 9 24 1000 22 16 7 17 12 24 1000 */
6 1000 10 12 5 22 18 11 1000 14 23 20 10 16 11 1000 6 21 24 5 21 6 1000 11 13 13 11 9 24 1000 22 16 7 17 12 24 1000
1 2 3 4 5 6 1 oo 10 12 5 22 18 2 11 oo 14 23 20 10 3 16 11 oo 6 21 24 4 5 21 6 oo 11 13 5 13 11 9 24 oo 22 6 16 7 17 12 24 oo ai : 5 10 6 5 9 7 summa=42 bi : 0 0 0 0 6 0 summa=6 1 2 3 4 5 6 1 oo 5 7 0 11 13 2 1 oo 4 13 4 0 3 10 5 oo 0 9 18 4 0 16 1 oo 0 8 5 4 2 0 15 oo 13 6 9 0 10 5 11 oo D= {(1, 4) = 5, (2, 6) = 9, (3, 4) = 5, (4, 1) = 1, (4, 5) = 4, (5, 3) = 3, (6, 2) = 7, } Dyga vetvlenia: (2, 6); h=48 Nizhnaa granica=57 ====================================================== 1 2 3 4 5 1 oo 5 7 0 11 3 10 5 oo 0 9 4 0 16 1 oo 0 5 4 2 0 15 oo 6 9 0 10 5 11 ai : 0 0 0 0 5 summa=5 bi : 0 2 0 0 0 summa=2 1 2 3 4 5 1 oo 3 7 0 11 3 10 3 oo 0 9 4 0 14 1 oo 0 5 4 0 0 15 oo 6 4 oo 5 0 6 D= {(1, 4) = 3, (3, 4) = 3, (4, 1) = 4, (4, 5) = 6, (5, 2) = 3, (5, 3) = 1, (6, 4) = 4, } Dyga vetvlenia: (4, 5); h=55 Nizhnaa granica=61 ====================================================== 1 2 3 4 1 oo 3 7 0 3 10 3 oo 0 5 4 0 0 15 6 4 oo 5 0 ai : 0 0 0 0 summa=0 bi : 4 0 0 0 summa=4 1 2 3 4 1 oo 3 7 0 3 6 3 oo 0 5 0 0 0 oo 6 0 oo 5 0 D= {(1, 4) = 3, (3, 4) = 3, (5, 1) = 0, (5, 2) = 3, (5, 3) = 5, (6, 1) = 0, (6, 4) = 0, } Dyga vetvlenia: (5, 3); h=59 Nizhnaa granica=64 ====================================================== 1 2 4 1 oo 3 0 3 6 3 0 6 0 oo 0 ai : 0 3 0 summa=3 bi : 0 0 0 summa=0 1 2 4 1 oo 3 0 3 3 0 oo 6 0 oo 0 D= {(1, 4) = 3, (3, 2) = 6, (6, 1) = 3, (6, 4) = 0, } Dyga vetvlenia: (3, 2); h=62 Nizhnaa granica=68 ====================================================== 1 4 1 oo 0 6 0 0 ai : 0 0 summa=0 bi : 0 0 summa=0 1 4 1 oo 0 6 0 oo D= {(1, 4) = 2000000000, (6, 1) = 2000000000, } Dyga vetvlenia: (1, 4); h=62 ====================================================== 1 6 0 ai : 0 summa=0 bi : 0 summa=0 1 6 0 D= {(6, 1) = 2000000000, } Dyga vetvlenia: (6, 1); h=62 ====================================================== Z= (48 55 59 62 62 62 ) Z_= (57 61 64 68 ) 2 6 >> 4 5 >> 5 3 >> 3 2 >> 1 4 >> 6 1 Dlina=62 (62), (62) ///////////////////////////// ------------Vetvlenie begin------------ Vetv (2, 6) 1 2 3 4 5 6 1 oo 10 12 5 22 18 2 11 oo 14 23 20 oo 3 16 11 oo 6 21 24 4 5 21 6 oo 11 13 5 13 11 9 24 oo 22 6 16 7 17 12 24 oo ai : 5 11 6 5 9 7 summa=43 bi : 0 0 0 0 6 8 summa=14 1 2 3 4 5 6 1 oo 5 7 0 11 5 2 0 oo 3 12 3 oo 3 10 5 oo 0 9 10 4 0 16 1 oo 0 0 5 4 2 0 15 oo 5 6 9 0 10 5 11 oo D= {(1, 4) = 5, (2, 1) = 3, (3, 4) = 5, (4, 1) = 0, (4, 5) = 3, (4, 6) = 5, (5, 3) = 3, (6, 2) = 7, } Dyga vetvlenia: (6, 2); h=57 Nizhnaa granica=64 ====================================================== 1 3 4 5 6 1 oo 7 0 11 5 2 0 3 12 3 oo 3 10 oo 0 9 10 4 0 1 oo 0 0 5 4 0 15 oo 5 ai : 0 0 0 0 0 summa=0 bi : 0 0 0 0 0 summa=0 1 3 4 5 6 1 oo 7 0 11 5 2 0 3 12 3 oo 3 10 oo 0 9 10 4 0 1 oo 0 0 5 4 0 15 oo 5 D= {(1, 4) = 5, (2, 1) = 3, (3, 4) = 9, (4, 1) = 0, (4, 5) = 3, (4, 6) = 5, (5, 3) = 5, } Dyga vetvlenia: (3, 4); h=57 Nizhnaa granica=66 ====================================================== 1 3 5 6 1 oo 7 11 5 2 0 3 3 oo 4 0 1 0 0 5 4 0 oo 5 ai : 5 0 0 0 summa=5 bi : 0 0 0 0 summa=0 1 3 5 6 1 oo 2 6 0 2 0 3 3 oo 4 0 oo 0 0 5 4 0 oo 5 D= {(1, 6) = 2, (2, 1) = 3, (4, 1) = 0, (4, 5) = 3, (4, 6) = 0, (5, 3) = 6, } Dyga vetvlenia: (5, 3); h=62 Nizhnaa granica=68 ====================================================== 1 5 6 1 oo 6 0 2 0 3 oo 4 0 0 0 ai : 0 0 0 summa=0 bi : 0 3 0 summa=3 1 5 6 1 oo 3 0 2 0 0 oo 4 0 oo 0 D= {(1, 6) = 3, (2, 1) = 0, (2, 5) = 3, (4, 1) = 0, (4, 6) = 0, } Dyga vetvlenia: (1, 6); h=65 Nizhnaa granica=68 ====================================================== 1 5 2 0 0 4 0 oo ai : 0 0 summa=0 bi : 0 0 summa=0 1 5 2 oo 0 4 0 oo D= {(2, 5) = 2000000000, (4, 1) = 2000000000, } Dyga vetvlenia: (2, 5); h=65 ====================================================== 1 4 0 ai : 0 summa=0 bi : 0 summa=0 1 4 0 D= {(4, 1) = 2000000000, } Dyga vetvlenia: (4, 1); h=65 ====================================================== Z= (57 57 62 65 65 65 ) Z_= (64 66 68 68 ) 6 2 >> 3 4 >> 5 3 >> 1 6 >> 2 5 >> 4 1 Dlina=62 (65), (65) Vetv (2, 6) ------------Vetvltnie end------------ ///////////////////////////// ------------Vetvlenie begin------------ Vetv (4, 5) 1 2 3 4 5 6 1 oo 10 12 5 22 18 2 11 oo 14 23 20 10 3 16 11 oo 6 21 24 4 5 21 6 oo oo 13 5 13 11 9 24 oo 22 6 16 7 17 12 24 oo ai : 5 10 6 5 9 7 summa=42 bi : 0 0 0 0 10 0 summa=10 1 2 3 4 5 6 1 oo 5 7 0 7 13 2 1 oo 4 13 0 0 3 10 5 oo 0 5 18 4 0 16 1 oo oo 8 5 4 2 0 15 oo 13 6 9 0 10 5 7 oo D= {(1, 4) = 5, (2, 5) = 5, (2, 6) = 8, (3, 4) = 5, (4, 1) = 2, (5, 3) = 3, (6, 2) = 7, } Dyga vetvlenia: (2, 6); h=52 Nizhnaa granica=60 ====================================================== 1 2 3 4 5 1 oo 5 7 0 7 3 10 5 oo 0 5 4 0 16 1 oo oo 5 4 2 0 15 oo 6 9 0 10 5 7 ai : 0 0 0 0 5 summa=5 bi : 0 2 0 0 2 summa=4 1 2 3 4 5 1 oo 3 7 0 5 3 10 3 oo 0 3 4 0 14 1 oo oo 5 4 0 0 15 oo 6 4 oo 5 0 0 D= {(1, 4) = 3, (3, 4) = 3, (4, 1) = 5, (5, 2) = 3, (5, 3) = 1, (6, 4) = 0, (6, 5) = 3, } Dyga vetvlenia: (4, 1); h=61 Nizhnaa granica=66 ====================================================== 2 3 4 5 1 3 7 0 5 3 3 oo 0 3 5 0 0 15 oo 6 oo 5 0 0 ai : 3 0 0 0 summa=3 bi : 0 0 0 0 summa=0 2 3 4 5 1 0 4 oo 2 3 3 oo 0 3 5 0 0 15 oo 6 oo 5 0 0 D= {(1, 2) = 2, (3, 4) = 3, (5, 2) = 0, (5, 3) = 4, (6, 4) = 0, (6, 5) = 2, } Dyga vetvlenia: (5, 3); h=64 Nizhnaa granica=68 ====================================================== 2 4 5 1 0 oo 2 3 3 0 3 6 oo 0 0 ai : 0 0 0 summa=0 bi : 0 0 0 summa=0 2 4 5 1 0 oo 2 3 3 0 oo 6 oo 0 0 D= {(1, 2) = 5, (3, 4) = 3, (6, 4) = 0, (6, 5) = 2, } Dyga vetvlenia: (1, 2); h=64 Nizhnaa granica=69 ====================================================== 4 5 3 0 oo 6 0 0 ai : 0 0 summa=0 bi : 0 0 summa=0 4 5 3 0 oo 6 oo 0 D= {(3, 4) = 2000000000, (6, 5) = 2000000000, } Dyga vetvlenia: (3, 4); h=64 ====================================================== 5 6 0 ai : 0 summa=0 bi : 0 summa=0 5 6 0 D= {(6, 5) = 2000000000, } Dyga vetvlenia: (6, 5); h=64 ====================================================== Z= (52 61 64 64 64 64 ) Z_= (60 66 68 69 ) 2 6 >> 4 1 >> 5 3 >> 1 2 >> 3 4 >> 6 5 Dlina=62 (64), (64) ///////////////////////////// ------------Vetvlenie begin------------ Vetv (4, 5), (2, 6) 1 2 3 4 5 6 1 oo 10 12 5 22 18 2 11 oo 14 23 20 oo 3 16 11 oo 6 21 24 4 5 21 6 oo oo 13 5 13 11 9 24 oo 22 6 16 7 17 12 24 oo ai : 5 11 6 5 9 7 summa=43 bi : 0 0 0 0 9 8 summa=17 1 2 3 4 5 6 1 oo 5 7 0 8 5 2 0 oo 3 12 0 oo 3 10 5 oo 0 6 10 4 0 16 1 oo oo 0 5 4 2 0 15 oo 5 6 9 0 10 5 8 oo D= {(1, 4) = 5, (2, 1) = 0, (2, 5) = 6, (3, 4) = 5, (4, 1) = 0, (4, 6) = 5, (5, 3) = 3, (6, 2) = 7, } Dyga vetvlenia: (6, 2); h=60 Nizhnaa granica=67 ====================================================== 1 3 4 5 6 1 oo 7 0 8 5 2 0 3 12 0 oo 3 10 oo 0 6 10 4 0 1 oo oo 0 5 4 0 15 oo 5 ai : 0 0 0 0 0 summa=0 bi : 0 0 0 0 0 summa=0 1 3 4 5 6 1 oo 7 0 8 5 2 0 3 12 0 oo 3 10 oo 0 6 10 4 0 1 oo oo 0 5 4 0 15 oo 5 D= {(1, 4) = 5, (2, 1) = 0, (2, 5) = 6, (3, 4) = 6, (4, 1) = 0, (4, 6) = 5, (5, 3) = 5, } Dyga vetvlenia: (2, 5); h=60 Nizhnaa granica=66 ====================================================== 1 3 4 6 1 oo 7 0 5 3 10 oo 0 10 4 0 1 oo 0 5 4 0 15 5 ai : 0 0 0 0 summa=0 bi : 0 0 0 0 summa=0 1 3 4 6 1 oo 7 0 5 3 10 oo 0 10 4 0 1 oo 0 5 4 0 15 oo D= {(1, 4) = 5, (3, 4) = 10, (4, 1) = 4, (4, 6) = 5, (5, 3) = 5, } Dyga vetvlenia: (3, 4); h=60 Nizhnaa granica=70 ====================================================== 1 3 6 1 oo 7 5 4 0 1 0 5 4 0 oo ai : 5 0 0 summa=5 bi : 0 0 0 summa=0 1 3 6 1 oo 2 0 4 0 oo 0 5 4 0 oo D= {(1, 6) = 2, (4, 1) = 4, (4, 6) = 0, (5, 3) = 6, } Dyga vetvlenia: (5, 3); h=65 Nizhnaa granica=71 ====================================================== 1 6 1 oo 0 4 0 0 ai : 0 0 summa=0 bi : 0 0 summa=0 1 6 1 oo 0 4 0 oo D= {(1, 6) = 2000000000, (4, 1) = 2000000000, } Dyga vetvlenia: (1, 6); h=65 ====================================================== 1 4 0 ai : 0 summa=0 bi : 0 summa=0 1 4 0 D= {(4, 1) = 2000000000, } Dyga vetvlenia: (4, 1); h=65 ====================================================== Z= (60 60 60 65 65 65 ) Z_= (67 66 70 71 ) 6 2 >> 2 5 >> 3 4 >> 5 3 >> 1 6 >> 4 1 Dlina=62 (65), (65) Vetv (4, 5), (2, 6) ------------Vetvltnie end------------ Vetv (4, 5) ------------Vetvltnie end------------ 1 2 3 4 5 6 1 oo 10 12 5 22 18 2 11 oo 14 23 20 10 3 16 11 oo 6 21 24 4 5 21 6 oo 11 13 5 13 11 9 24 oo 22 6 16 7 17 12 24 oo Pyt 1: 2 6 >> 4 5 >> 5 3 >> 3 2 >> 1 4 >> 6 1. Dlina=62 Pyt 2: 6 2 >> 3 4 >> 5 3 >> 1 6 >> 2 5 >> 4 1. Dlina=65 -> Vetvlenie po dyge (2, 6) Pyt 3: 2 6 >> 4 1 >> 5 3 >> 1 2 >> 3 4 >> 6 5. Dlina=64 -> Vetvlenie po dyge (4, 5) Pyt 4: 6 2 >> 2 5 >> 3 4 >> 5 3 >> 1 6 >> 4 1. Dlina=65 -> Vetvlenie po dyge (4, 5), (2, 6) Dlina=62 //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////
sh: 1: pause: not found