Решение задачи о коммивояжере

name_city[28] = "Волгоград";

x0=10;y0=10;// смещение карты относительно левого верхнего угла окна

koord[0][0]=x0+225;// Санкт-Петербург

koord[0][1]=y0+54;

koord[1][0]=x0+148; //Псков

koord[1][1]=y0+60;

koord[2][0]=x0+195; // Новгород

koord[2][1]=y0+92;

koord[3][0]=x0+93; // Смоленск

koord[3][1]=y0+171;

koord[4][0]=x0+191; //Тверь

koord[4][1]

=y0+193;

koord[5][0]=x0+301; //Вологда

koord[5][1]=y0+200;

koord[6][0]=x0+261; //Ярославль

koord[6][1]=y0+231;

koord[7][0]=x0+279;//Кострома

koord[7][1]=y0+248;

koord[8][0]=x0+181;//Москва

koord[8][1]=y0+241;

koord[9][0]=x0+76;//Брянск

koord[9][1]=y0+240;

koord[10][0]=x0+133;//Калуга

koord[10][1]=y0+245;

koord[11][0]=x0+256;//Иваново

koord[11][1]=y0+264;

koord[12][0]=x0+88;//Орел

koord[12][1]=y0+275;

koord[13][0]=x0+139;//Тула

koord[13][1]=y0+272;

koord[14][0]=x0+227;//Владимир

koord[14][1]=y0+274;

koord[15][0]=x0+55;//Курск

koord[15][1]=y0+297;

koord[16][0]=x0+176;//Рязань

koord[16][1]=y0+297;

koord[17][0]=x0+29;//Белгород

koord[17][1]=y0+328;

koord[18][0]=x0+121;//Липецк

koord[18][1]=y0+338;

koord[19][0]=x0+276;//Нижний Новгород

koord[19][1]=y0+322;

koord[20][0]=x0+92;//Воронеж

koord[20][1]=y0+353;

koord[21][0]=x0+149;//Тамбов

koord[21][1]=y0+364;

koord[22][0]=x0+307;//Чебоксары

koord[22][1]=y0+373;

koord[23][0]=x0+237;//Саранск

koord[23][1]=y0+388;

koord[24][0]=x0+212;//Пенза

koord[24][1]=y0+408;

koord[25][0]=x0+280;//Ульяновск

koord[25][1]=y0+429;

koord[26][0]=x0+184;//Саратов

koord[26][1]=y0+456;

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;

 Скачать реферат