Текущ брой на Списание ИнфоМан
 


Зимни математически състезания 2001 - Задача SEGS

Уловието на задачата може да прочетете тук.

Решение

Решение на тази задача е представено в брой 19 на списание Infoman. Тук предлагаме  алтернативно решение, използващо граф и отново основаващо се на динамично оптимиране.

Нека броя на отсечките е N и с liе означена отсечката с номер i(1 ≤ i N). Създава се ориентиран граф, като (i, j) Î Е ó отсечката liсе съдържа изцяло в отсечката ljи са различни. Не е трудно да се докаже, че в този граф няма цикли. Ако се допусне, че съществува цикъл от поне три върха, който започва от връх с номер i, минава през k и завършва в j. Това означава, че отсечка i се съдържа в k, k се съдържа в j и j се съдържа в i. Но това е невъзможно, тъй като сме приели че i се съдържа j, следователно графа е ацикличен.

Не е трудно да се съобрази, че дължината на най-дългата редица от последователно вложени отсечки е равна на най-дългия път в графа. Поради ацикличността на графа, може да се използва един ефективен алгоритъм, основаващ се на динамично оптимиране със сложност О(N+M), където М е броя на ребрата.

За всеки връх pсе пази стойност f[p], която показва колко е най-дългия път, който започва с върха p. За всички върхове, от които не излизат ребра функцията f има стойност 1. Алгоритъмът протича в няколко стъпки:

1.       Избира се връх, от който не излизат ребра. Винаги има поне един такъв. Това е така, защото графа е ацикличен.

2.       Нека p е избрания връх, а q е връх, от който излиза ребро към p. Тогава ако f[q] < f[p]+1 на f[q] се присвоява стойността f[p]+1. След като се разгледат всички върхове q ребрата от тях към p се премахват от графа.

3.       Ако в графа все още има ребра се преминава към стъпка 2. В противен случай се преминава към стъпка 4. Функцията f съдържа най-дългия път, започващ от всеки един връх

4.       От всички върхове се избира този, от който излиза най-дългия път в графа. Това е отговора на задачата.

Ето така със сложност O(N+M) се намира най-дълъг път в ацикличен граф. Ако се използва матрица на съседство сложността е O(N2).

Примерна реализация


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

#define MAXN 500
// checks if the segment x is in the segment y
#define IS_IN( x, y ) ( ( line[x].a > line[y].a ) && \
                              ( line[x].b < line[y].b ) ) 

struct LINE {
     int a; // begin
     int b; // end
} line[MAXN];

typedef struct VERTEX* link;

struct VERTEX { 
     int vert;
     link next;
} *V[MAXN];

/* F[i] -- length of the maximum 
             path beginning from i */

int n, mInd, prev[MAXN], F[MAXN]; 

/* Reading input */

void readInput( void )
{
     int i;
     FILE *fin;

     fin = stdin;
     fscanf( fin, "%d", &n );

     for( i = 0; i < n; i++ ) {
          fscanf( fin, "%d %d", &line[i].a, &line[i].b );
          V[i] = NULL; 
     }

     fclose( fin );
}

/* Adds edge (i, j) */

void add_edge( int i, int j )
{
     link t = ( link ) malloc( sizeof( *t ) );

     t->vert = j;
     t->next = V[i];

     V[i] = t;
}

/* Depth-First Search which calculates the 
   values of F[]*/

void DFS( int i )
{
     int maxD, dist;
     link t = V[i];

     if( F[i] > 0 ) return;

     maxD = F[i];

     while( t != NULL ) { // for each neighbour
          int k = t->vert;

          DFS( k );
          dist = F[k] + 1;

          if( dist > maxD ) {
               maxD = dist;
               prev[i] = k;
          }

          // go to the next neighbour
          t = t->next; 
     }

     F[i] = maxD;
}

/* Outputs the solution */

void printSol( void )
{
     FILE *fout;

     fout = stdout;
     fprintf( fout, "%d\n", F[mInd] + 1 );

     while( prev[mInd] >= 0 ) {
          fprintf( fout, "%d ", mInd + 1 );
          mInd = prev[mInd];
     }

     fprintf( fout, "%d\n", mInd + 1 );
     fclose( fout );
}

void solve( void )
{
     int i;

     for( i = 0; i < n; i++ )
          prev[i] = -1;

     for( i = 0; i < n; i++ )
          if( F[i] == 0 ) DFS( i );

     for( i = 0, mInd = 0; i < n; i++ )
          if( F[i] > F[mInd] ) mInd = i;
}

/* Creates the graph */

void createGraph( void )
{
     int i, j;

     for( i = 0; i < n; i++ )
          for( j = 0; j < n; j++ ) 
               if( IS_IN( i, j ) ) 
                    add_edge( i, j );
}

int main( void )
{
     readInput();
     createGraph();

     solve();
     printSol();

     return 0;
}


Автор: Владимир Ангелов


обратно към текущ брой