Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 12.01.2011, 19:40
Новичок

Отправить личное сообщение для Ihtiandr Посмотреть профиль Найти все сообщения от Ihtiandr
 
Регистрация: 12.01.2011
Сообщений: 1

помогите с алгоритмом задача на связанность маршрутов
Доброго всем время суток уважаемые дамы и господа.
Помогите найти алгоритм решения задачи вот пример
Во входном файле
3-4
4-9
8-0
2-3
5-6
2-9
5-9
7-3
4-8
5-6
0-2
6-1
в выходном файле выводится
3-4
4-9
8-0
2-3
5-6
5-9
7-3
4-8
6-1
Т.е. надо проверить на нахождение лишнего маршрута и каждый последующий маршрут проверяется с учётом задания предыдущих маршрутов т.е в примере мы избавились от 2-9 т.к. мы можем дойти от2до9 без этого указанного маршрута потому что у нас перед этим стоит2-3 т.е. мы можем от2 перейти к 3 потом 3-4 от3 к 4 и 4-9 от4 к 9 по такому же принципу мы избавились и от 5-6 и 0-2
так же мы можем переходить как и от 0-8 так и от8-0 (ограничение до числа1000)
Помогите пожалуйста разобраться с алгоритмом.
И как этот алгоритм написать без графов?
  #2  
Старый 13.01.2011, 03:02
Пользователь

Отправить личное сообщение для lordKelvin Посмотреть профиль Найти все сообщения от lordKelvin
 
Регистрация: 25.01.2010
Сообщений: 51

Код:
#include <stdio.h>

int *reallocate( int *buf, int size, int nsize )
{
    int *tmp = new int [ nsize ];
    memcpy( buf, tmp, size * sizeof( int ) );
    delete []buf;
    return tmp;
}

int main( int argc, char *argv[] )
{
    int mbuf = 16, ibuf = 0, a, b;
    int **buf = new int * [ mbuf ];
    while( scanf( "%d-%d", &a, &b ) == 2 )
    {
        for( int i = 0;; i++ )
        {
            if( i == a.i )
            {
                buf[ ibuf ] = new int [ 16 ];
                buf[ ibuf ][ 0 ] = 16;
                buf[ ibuf ][ 1 ] = 3;
                buf[ ibuf ][ 2 ] = a;
                buf[ ibuf ][ 3 ] = b;
                if( ++ibuf >= mbuf )
                {
                    buf = ( int ** )reallocate( ( int * )buf, mbuf, mbuf + 16 );
                    mbuf += 16;
                }
                printf( "%d-%d\r\n", a, b );
                break;
            }
            bool ain = false, bin = false;
            for( int j = 2; j < buf[ ibuf ][ buf[ ibuf ][ 1 ] ]; j++ )
            {
                ain |= a == buf[ ibuf ][ j ];
                bin |= b == buf[ ibuf ][ j ];
            }
            if( ain && bin )
                break;
            if( !ain && !bin )
                continue;
            printf( "%d-%d\r\n", a, b );
            if( ain ) buf[ ibuf ][ buf[ ibuf ][ 1 ]++ ] = b;
            if( bin ) buf[ ibuf ][ buf[ ibuf ][ 1 ]++ ] = a;
            if( buf[ ibuf ][ 1 ] >= buf[ ibuf ][ 0 ] )
            {
                buf[ ibuf ] = reallocate( buf[ ibuf ], buf[ ibuf ][ 1 ], buf[ ibuf ][ 1 ] + 16 );
                buf[ ibuf ][ 1 ] += 16;
            }
        }
    }
    delete buf;
}
 

« Задача 524 | - »

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
помогите с алгоритмом гость Математические алгоритмы 3 28.04.2010 09:26
Помогите с Волновым алгоритмом. Vasilevs Графы 1 20.04.2009 00:30
Помогите с Волновым алгоритмом. Vasilevs Математические алгоритмы (другое) 0 19.04.2009 22:43
Помогите с алгоритмом Никто Вычислительная геометрия 2 30.12.2007 22:24
Помогите с алгоритмом гость Графы 4 09.08.2007 19:59