Зимни математически състезания 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;
}
Автор: Владимир Ангелов
обратно към текущ брой
|