Cod sursa(job #14310)

Utilizator rusRus Sergiu rus Data 8 februarie 2007 18:31:19
Problema Asmax Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <stdio.h>
#define dim 16001

typedef struct nod
{
    int x;
    nod *adr_urm;
}*pnod;

pnod l[dim];

int n,m;
int s[dim], v[dim], niv[dim];
long int suma[dim];


void citire ();
void add ( int i, int j );
void df ( int i );
void afisare ();


int main ()
{
    freopen ( "asmax.in", "r", stdin );
    freopen ( "asmax.out", "w", stdout );

    citire ();
    df ( 1 );
    afisare ();

    return 0;
}

void citire ()
{
    int i, j, x, y;

    scanf ( "%d %d", &n,&m );
    for ( i = 1; i <= n; i++ )
    {
	scanf ( "%d", &v[i] );
	suma[i] = v[i];
    }


    for ( i = 1; i <= m; i++ )
    {
	scanf ( "%d %d", &x, &y );
	add ( x, y );

	add ( y, x );

    }
}

void add ( int i, int j )
{
    pnod p = new nod;

    p->x = j;
    p->adr_urm = l[i];
    l[i] = p;
}

void df ( int nod )
{
    pnod p;

    s[nod] = 1;
   // printf ( "%d ", nod );

    for ( p = l[nod]; p; p = p->adr_urm )
        if ( !s[p->x] )
        {
            niv[p->x] = niv[nod] + 1;
            df ( p->x );
        }

    for ( p = l[nod]; p; p = p->adr_urm )
	if ( niv[p->x] > niv[nod] && suma[p->x]>0)
            suma[nod] += suma[p->x];
}

void afisare ()
{
    int i;
    pnod p;
    long int max;

    max = -32221;
    for ( i = 1; i <= n; i++ )
        if ( suma[i] > max )
            max = suma[i];



    printf ( "%ld", max );

}