VPF::Проблема с графами - Форум программистов

Doc_d0s

Дата 28.5.2005, 18:50 (ссылка)

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

Загрузка ...

Бывалый

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

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

Суть:
Задана система 2хсторонних дорог, определить можно ли построить ещё три новые дороги, из данного города добраться до всех остальных проезжая расстояние не больше n. данные о новых дорогах вводяться с клавиатуры.

Код


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

#define dataEr    printf("\t\t\t\t!!!ERROR!!! \n\n\t\tFILE IS EMPTY or no match symbolyc information!\n\n")
#define FileEr    printf("\t\t\t\t!!!ERROR!!! \n\n\t\tNo such fiLe or DirEctOry\n\n")
#define QUIT printf("\nDo you want to close this program?(y/n)\t"); if( getche()=='y' ) exit(0);

int *res;
int **graph;
int n;   

int read_matr();
void destroy_matr();
void deep_matr (int v);
void main_func();

void main()
{
    while(1)
    {
        main_func();
        QUIT;
        getch();
    }
}
int read_matr()
{ 
    FILE *f;
    int i, j;
    if((f=fopen ("C:\\f.dat", "r"))==NULL)
    {    
        FileEr;
        return 0;
    }
    fscanf(f,"%d", &n);
    printf("The size of matrix is: %dx%d\n",n,n);
    graph=new int*[n];
    for (i=0; i<n; ++i) 
        graph[i]=new int[n]; 
    for (i=0; i<n; ++i) 
        for(j=0;j<n;++j)
        {
            if(fscanf(f, "%d", &graph[i][j])==EOF)
            {
                dataEr;
                fclose(f);
                return 0;
            }
        }
    fclose(f);

    res=new int[n]; 
    for (i=0; i<n; ++i) res[i]=0;
    return 1;
}

void destroy_matr()
{
    for (int i=0; i<n;i++)
        delete [] graph[i];
    delete [] graph; 
    delete [] res;
}

void deep_matr (int v)
{
    cout<<"Node: "<< v+1 << endl;  //Âûâîä ïðîéäåííîé âåðøèíû. 
    res[v]=1; 
    for (int i=0; i<n; ++i)   //Ïîèñê ñìåæíûõ íå ïðîéäåííûõ âåðøèí.
    {
        if (graph[v][i] && !res[i]) 
            deep_matr(i);
    }
}
void main_func()
{
    int k=0;
    while(1)
    {
        system("cls");
        if(!read_matr())
            exit(0);
        while(1)
        {
            printf("Please enter the summ way:\t");
            scanf("%d",&k);
            if(k<=n)
                break;
            system("cls");
            printf("\n\t\t!!!Your data is illegal. Value must before %d!!!\n",n);
            getch();
            system("cls");
        }
        deep_matr(k-1);
        destroy_matr();
        break;
    }
}

Тут я токо обхожу граф(задается матрице смежности), с нужной вершины. Хелп. Непонятна сама задача.

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

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

kometa_triatlon

Дата 28.5.2005, 23:16 (ссылка)

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

Загрузка ...

Опытный

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

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

А ты сам понял что сказал smile

Цитата

Задана система 2хсторонних дорог, определить можно ли построить ещё три новые дороги, из данного города добраться до всех остальных проезжая расстояние не больше n.

Я что-то не понял, что это означает...

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

Всё очень просто: сказки обман,
Солнечный остров скрылся в туман,
Замков воздушных не носит земля,
Кто-то ошибся, ты или я.
--------------
Программирование - самое большое удовольствие, которое вы можете получить, будучи одетым.

Doc_d0s

Дата 29.5.2005, 19:31 (ссылка)

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

Загрузка ...

Бывалый

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

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

ЭТО ЗАДАЧА!!! smile

Её надо помочь мне решить smile

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

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

Doc_d0s

Дата 29.5.2005, 21:47 (ссылка)

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

Загрузка ...

Бывалый

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

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

2kometa_triatlon
Вот именно я процитировал методу с лабами, а каково мне вот я и спросил у знающего народа,как и что smile

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

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

kometa_triatlon

Дата 29.5.2005, 22:11 (ссылка)

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

Загрузка ...

Опытный

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

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

Так это не сюда, это в филологам smile

Сначала бы понять, что это означает, а потом программировать...

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

Doc_d0s

Дата 29.5.2005, 22:51 (ссылка)

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

Загрузка ...

Бывалый

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

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

2kometa_triatlon
smile

)))))))))))))
К делу. Я написал проверку на три дороги, осталось написать на
(проходя путь не более n):
Ваши предложения?

Код


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

#define dataEr    printf("\t\t\t\t!!!ERROR!!! \n\n\t\tFILE IS EMPTY or no match symbolyc information!\n\n")
#define FileEr    printf("\t\t\t\t!!!ERROR!!! \n\n\t\tNo such fiLe or DirEctOry\n\n")
#define QUIT printf("\nDo you want to close this program?(y/n)\t"); if( getche()=='y' ) exit(0);

int *res;
int **graph;
int n;   

int read_matr();
void check_1(int *a,int n);
void destroy_matr();
void deep_matr (int v);
void main_func();

void main()
{
    while(1)
    {
        main_func();
        QUIT;
        getch();
    }
}
int read_matr()
{ 
    FILE *f;
    int i, j;
    if((f=fopen ("C:\\f.dat", "r"))==NULL)
    {    
        FileEr;
        return 0;
    }
    fscanf(f,"%d", &n);
    printf("The size of matrix is: %dx%d\n",n,n);
    graph=new int*[n];
    for (i=0; i<n; ++i) 
        graph[i]=new int[n]; 
    for (i=0; i<n; ++i) 
        for(j=0;j<n;++j)
        {
            if(fscanf(f, "%d", &graph[i][j])==EOF)
            {
                dataEr;
                fclose(f);
                return 0;
            }
        }
    fclose(f);

    res=new int[n]; 
    for (i=0; i<n; ++i) res[i]=0;
    return 1;
}

void destroy_matr()
{
    for (int i=0; i<n;i++)
        delete [] graph[i];
    delete [] graph; 
    delete [] res;
}

void deep_matr (int v)
{
    cout<<"Node: "<< v+1 << endl;  //Âûâîä ïðîéäåííîé âåðøèíû. 
    res[v]=1; 
    for (int i=0; i<n; ++i)   //Ïîèñê ñìåæíûõ íå ïðîéäåííûõ âåðøèí.
    {
        if (graph[v][i] && !res[i]) 
            deep_matr(i);
    }
}
void main_func()
{
    int k=0;
    while(1)
    {
        system("cls");
        if(!read_matr())
            exit(0);
        while(1)
        {
            printf("Please enter the summ way:\t");
            scanf("%d",&k);
            if(k<=n)
                break;
            system("cls");
            printf("\n\t\t!!!Your data is illegal. Value must before %d!!!\n",n);
            getch();
            system("cls");
        }
        check_1(graph[0],n);
        deep_matr(k-1);
        destroy_matr();
        break;
    }
}
int sum(int*a, int n)
{
    int s=0;
    for(int i=0;i<n;i++)
        s=s+*(a+i);
    return s;
}
void check_1(int *a,int n)
{
    for(int i=0; i<n;i++)
        if(!sum(a+i,n)<=n-3)
        {
            printf("\t\tWe may build three roads\n");
            return;
        }
        printf("\t\tThere are enought roads\n");
}

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

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

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