VPF::каркас гафа с минимальной суммой

Doc_d0s

Дата 24.10.2005, 13:05 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 206
Регистрация: 15.12.2004
Где: в кресле

Репутация: 2
Всего: 3

нужна информация по сей теме

--------------------

Админ- это вождь Apache'й :)

pablo

Дата 24.10.2005, 14:50 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 320
Регистрация: 12.2.2005
Где: Вильнюс, Литва

Репутация: 4
Всего: 6

используй Boost, там есть всё что надо для работы с графами.
Струкруры данных и базовые алгоритмы нахождения крадчайших путей, и ещё многое другое.

Dowload from www.boost.org

--------------------

Первый блин всегда похож на сферу, иногда бывает и куб.

Doc_d0s

Дата 24.10.2005, 17:09 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 206
Регистрация: 15.12.2004
Где: в кресле

Репутация: 2
Всего: 3

ладно прога почти готова, если бы не одно но....
вылетает ошибка в конце подозрение на дин память.

Код


#include <conio.h>
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>

const n=8;
int p[n][n]; 
int a[n][n];
int **d;
        

int kraskal(int **d,int*res,int n);


int main()
{
        int i,j,m;
        int *res=new int [n*2];
        int sum=0;
        FILE *f;
        d=new int* [n];
        for(i=0;i<n;i++)
        {
            d[i]=new int [n];
        }
        system("cls");
        f=fopen("C:\\f.dat","r");
        for(i=0;i<n;i++)
             for(j=0;j<n;j++)
                        fscanf(f,"%d ",&a[i][j]);
        fclose(f);

        for(i=0;i<n;i++)
             for(j=0;j<n;j++)
                {
                        d[i][j]=a[i][j]; 
                        p[i][j]=0;
                            if(i==j)
                                p[i][j]=-1;
                    }
        for(i=0;i<n;i++)
             d[i][i]=0;                

        for(m=0;m<n;m++)
                for(i=0;i<n;i++)
                         for(j=0;j<n;j++)
                                 if (d[i][j]>d[i][m]+d[m][j])
                                    {
                                            d[i][j]=d[i][m]+d[m][j];
                                                if(i==j)
                                                    d[i][j]=35768;
                                                  p[i][j]=m+1; 
                                    }
        printf("\n\t\tMatrix of distance:\n");
        
        for(i=0;i<n;i++)
             {
                     for(j=0;j<n;j++)
                        printf("%d\t",d[i][j]);
                     printf("\n");
        }
        i=kraskal(d,res,n);
        printf("\nResult is:\t%d\n",i);
        getch();
        return 1;
}

void path(int i,int j)
{
    int k;
    k=p[i][j]-1;

    if (k!=0)
    {
            path(i,k);
            cout<<k+1<<"->";
            path(k,j);
   }
    else
            return;
}

int kraskal(int **d,int*res,int n)
{
    int *col=new int [n];
    int dmin;
    int l;
    int k,m,i1,j1,i,j;
    
   for(i=0;i<n;i++)
    {
        col[i]=i;
    }
    k=l=0;
    while(k<n-2)
    {
        dmin=35768;
        for(i1=0;i1<n-1;i1++)
        {
            for(j1=0;j1<n-1;j1++)
            {
                if(d[i1][j1]<dmin && col[i1]!=col[j1])
                {
                    dmin=d[i1][j1];
                    i=i1;
                    j=j1;
                }
            }
        }
        k++;
        l=l+dmin;
        *(res+k*n+0)=i;
        *(res+k*n+1)=j;
        j1=col[j];
        for(m=0;m<n;m++)    
        {
            if(col[m]==j1)
                col[m]=col[i];
        }
    }
    return l;
}

и содержимое файла f.dat:

35768 10 35768 35768 35768 35768 35768 35768
10 35768 20 35768 35768 60 35768 35768
35768 20 35768 30 35768 30 35768 35768
35768 35768 30 35768 40 35768 40 35768
35768 35768 35768 40 35768 35768 35768 10
35768 60 30 35768 35768 35768 35768 35768
35768 35768 35768 40 35768 35768 35768 10
35768 35768 35768 35768 10 35768 10 35768

Это сообщение отредактировал(а) Doc_d0s - 24.10.2005, 17:38

--------------------

Админ- это вождь Apache'й :)

Doc_d0s

Дата 24.10.2005, 18:40 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 206
Регистрация: 15.12.2004
Где: в кресле

Репутация: 2
Всего: 3

срочно плизз!! smile

--------------------

Админ- это вождь Apache'й :)

nikitao

Дата 24.10.2005, 19:03 (ссылка)

(нет голосов)

Загрузка ...

Кот-программист

Профиль
Группа: Завсегдатай
Сообщений: 1206
Регистрация: 30.8.2005
Где: Спб

Репутация: 1
Всего: 26

Код


#include <conio.h>
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>

Что-то "Шапка" кода меня весьма смущает??? smile

--------------------

Жизнь - печальная штука.

pablo

Дата 25.10.2005, 12:20 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 320
Регистрация: 12.2.2005
Где: Вильнюс, Литва

Репутация: 4
Всего: 6

Цитата

1:
2:
3:
4:

#include <conio.h>
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>

Что-то "Шапка" кода меня весьма смущает??? smile smile smile

Изза чего же ?

--------------------

Первый блин всегда похож на сферу, иногда бывает и куб.

Doc_d0s

Дата 25.10.2005, 13:29 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 206
Регистрация: 15.12.2004
Где: в кресле

Репутация: 2
Всего: 3

модеры закрывайте тему smile

решил, сам smile

)

--------------------

Админ- это вождь Apache'й :)

nikitao

Дата 25.10.2005, 15:34 (ссылка)

(нет голосов)

Загрузка ...

Кот-программист

Профиль
Группа: Завсегдатай
Сообщений: 1206
Регистрация: 30.8.2005
Где: Спб

Репутация: 1
Всего: 26

Цитата

Изза чего же ?

Просто зачем подключать iostream и stdio одновременно.stdio это же C а iostream это С++???

--------------------

Жизнь - печальная штука.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »