Программная реализация метода ветвей и границ

     koord[27][0]=x0+292;//Самара

     koord[27][1]=y0+491;

     koord[28][0]=x0+91;//Волгоград

     koord[28][1]=y0+506; 

     count_selected=0;

     myFont.CreateFont(17,0,0,0,500,false,false,false,0,0,0,0,0,"Courier Cyr");

     m_len="Выберите  несколько городов.";

     m_label.SetFont (&myFont);

     UpdateData(false); 

     for (int i=0; i < 29; i++)

     flag_select[i]=false;

     flag_draw=false;

     begin_point = -1;

     flag_Bpoint=false; 
 

     CStdioFile f1;

     f1.Open("table.ini",CFile::modeRead);

       for ( i=0; i < 29; i++)

     {

     tableAllCity[i][i]=0; 

     CString s1;

     f1.ReadString(s1);

     int j=i+1;

     int k=0;

     while (j<29 && k < s1.GetLength())

     {CString s2;

     while (s1[k] == ' ') k++;

     while (s1[k] != ' ')

     {   s2 += s1[k];    k++;}

     tableAllCity[j][i]=tableAllCity[i][j]=atoi(s2);

     j++;

     }

     } 

     return TRUE;  // return TRUE  unless you set the focus to a control

     } 

     void CKurs_LipinDlg::OnSysCommand(UINT nID, LPARAM lParam)

     {

     if ((nID & 0xFFF0) == IDM_ABOUTBOX)

     {

     CAboutDlg dlgAbout;

     dlgAbout.DoModal();

     }

     else

     {

     CDialog::OnSysCommand(nID, lParam);

     }

     } 

     // If you add a minimize button to your dialog, you will need the code below

     //  to draw the icon.  For MFC applications using the document/view model,

     //  this is automatically done for you by the framework. 

     void CKurs_LipinDlg::OnPaint()

     {

     if (IsIconic())

     {

     CPaintDC dc(this); // device context for painting 

     SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0); 

     // Center icon in client rectangle

     int cxIcon = GetSystemMetrics(SM_CXICON);

     int cyIcon = GetSystemMetrics(SM_CYICON);

     CRect rect;

     GetClientRect(&rect);

     int x = (rect.Width() - cxIcon + 1) / 2;

     int y = (rect.Height() - cyIcon + 1) / 2; 

     // Draw the icon

     dc.DrawIcon(x, y, m_hIcon);

     }

     else

     {

     CClientDC pDC(this);

     CDC temp;

     CBitmap bmp;

     bmp.LoadBitmap(IDB_BITMAP1);

     temp.CreateCompatibleDC (&pDC);

     temp.SelectObject(bmp); 

     for (int j=0;j<29;j++)

     {

     if (flag_select[j])

     {

     int x=koord[j][0]-x0;

     int y=koord[j][1]-y0; 

     temp.SelectStockObject (BLACK_BRUSH);

     temp.Ellipse(x-3,y-3,x+3,y+3);

     }

     }

     if (begin_point>=0)

     {

     int x=koord[begin_point][0]-x0;

     int y=koord[begin_point][1]-y0;

     CBrush br (RGB(255,0,0));

     temp.SelectObject (&br);

     temp.Ellipse(x-4,y-4,x+4,y+4); 

     } 

     if (flag_draw)

     {

     for (int i = 0; i < n; i++)

     {

     int x1 = koord[sel_city[min_path[i]-1]][0];

     int x2 = koord[sel_city[min_path[i+1]-1]][0];

     int y1 = koord[sel_city[min_path[i]-1]][1];

     int y2 = koord[sel_city[min_path[i+1]-1]][1]; 

     temp.MoveTo(x1-x0,y1-y0);

     temp.LineTo(x2-x0,y2-y0);

     } 

     CString s1; 

     m_list1.ResetContent();

     for (i=0;i < n; i++)

     {

     s1=name_city[sel_city[min_path[i]-1]];

     s1+=" - "+name_city[sel_city[min_path[i+1]-1]];

     CString s2;

     s2.Format("%d",table[min_path[i]-1][min_path[i+1]-1]);

     s1+=" ->"+s2;

     m_list1.AddString(s1); 

     }

     m_len.Format("Длина пути:\n%d км",min_path[n+1]);

     for (i=0;i < n; i++)

     {

     if (i % 2 != 0) m_list1.SetSel(i);

     }

     }

     else

     {

     m_len="Выберите  несколько городов."; 

     }

     UpdateData(false); 

     pDC.BitBlt(x0,y0,638,638,&temp,0,0,SRCCOPY); 

     CDialog::OnPaint();

     }

     } 

     // The system calls this to obtain the cursor to display while the user drags

     //  the minimized window.

     HCURSOR CKurs_LipinDlg::OnQueryDragIcon()

     {

     return (HCURSOR) m_hIcon;

     } 

     void CKurs_LipinDlg::OnLButtonDown(UINT nFlags, CPoint point)

     {

     for (int i=0;i<29;i++)

     {

     int x=point.x-koord[i][0],y=point.y-koord[i][1];

     if((x*x+y*y)<=7*7)

     {

     if (flag_Bpoint)

     {

     if (count_selected >= 13 && flag_select[i]==false)

     {

     MessageBox ("Нельзя выбрать более 13 городов  !!!\nВыберите выделенный город  или снимите выделение \nс одного  города и поставьте на другом.");

     flag_Bpoint=false;

     Invalidate(false);

     }

     else

     {

     begin_point=i;

     flag_Bpoint=false;

     if (flag_select[i]==false) count_selected++; 

     flag_select[i]=true;

     flag_draw=false;

     Invalidate(false);

     }

     }

     else

     {

     if (count_selected >= 13 && flag_select[i]==false)

     {

     MessageBox ("Нельзя выбрать более 13 городов !!!");

     }

     else

     {

     if (flag_select[i]==false) count_selected++;

     else

     {

     count_selected--;

     if (i == begin_point)

     {

     begin_point=-1;

     }

     }

     flag_select[i]=!flag_select[i];

     flag_draw=false;

     Invalidate(false);

     }

     }

     }

     }

     CDialog::OnLButtonDown(nFlags, point);

     } 

     void CKurs_LipinDlg::OnButton1()

     {

     m_list1.ResetContent(); 

     for (int i=0; i < 29; i++)

     flag_select[i]=false;

     flag_select[6]=true;

     flag_select[8]=true;

     flag_select[12]=true;

     flag_select[13]=true;

     flag_select[15]=true;

     flag_select[18]=true;

     flag_select[19]=true;

     flag_select[20]=true;

     flag_select[21]=true;

     flag_select[26]=true;

     flag_select[27]=true;

     flag_select[28]=true;

     flag_select[24]=true;

     count_selected=13;

     flag_draw=false;

     flag_Bpoint = false;

     begin_point = -1; 
 

     Invalidate(false); 

     } 

     void CKurs_LipinDlg::OnButton2()

     {

     m_list1.ResetContent(); 

     for (int i=0; i < 29; i++)

     flag_select[i]=false;

     flag_Bpoint = false;

     begin_point = -1;

     count_selected = 0;

     flag_draw = false;

     Invalidate (false); 

     } 

     void CKurs_LipinDlg::OnOK()

     {

     m_list1.ResetContent(); 

     n = count_selected; 

     if (n <=1)

     {

     MessageBox ("Пожалуйста, выберите не менее  2 городов.");

     return;

     }

     sel_city= new int[n];

     int count = 0;

     for (int i=0; i < 29; i++)

     if (flag_select[i]) sel_city[count++] = i; 

     for (i=0; i < n; i++)// ставим исходный город  на первое место в массиве

     if (sel_city[i] == begin_point)

     {

     int tmp = sel_city[0];

     sel_city[0] = sel_city[i];

     sel_city[i] = tmp;

     } 

     table = new int *[n];

     for (i=0; i<n; i++)

     table[i] = new int [n]; 

     for (i=0; i<n; i++)

       for (int j = 0; j < n; j++)

       {

     if (i>=j)

     {

     table[i][j]=table[j][i]=tableAllCity[sel_city[i]][sel_city[j]];

     }

       } 

     bool *flag = new bool[n];      //  заполнение  признаков посещения городов

     flag[0] = true;

     for (i=1; i < n; i++) flag[i]=false; 

     unsigned int *cur_path = new unsigned int[n+2];

     min_path = new unsigned int[n+2]; 

     //  заполнение матриц минимального  пути и текущего пути

     min_path[0] = min_path[n]=1;    min_path[n+1]=0;

     for (i=1; i < n; i++)

     {

     min_path[i]=i+1;  min_path[n+1]+=table[i-1][i];

     cur_path[i]=0;

     }  min_path[n+1] += table [min_path[n-1]-1] [min_path[n]-1 ]; 

     cur_path[n+1] =0;

     cur_path[0] = cur_path[n] = 1; 

     m_len="Пожалуйста, подождите:\nидут вычисления...";

     UpdateData(false); 

     recursiv (flag,cur_path, 1);    // вызов рекурсивной  функции*/