Cod sursa(job #1114438)

Utilizator taigi100Cazacu Robert taigi100 Data 21 februarie 2014 16:57:01
Problema Asmax Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<stdio.h>
#include<list>

#define MaxN 16005
#define maxw(a,b) a>b ? a:b

using namespace std;

int n,maxv,v[MaxN],best[MaxN];
bool viz[MaxN];

list<int> G[MaxN];

void DF(int node)
{
    viz[node] = 1;
    for(list<int>::iterator it = G[node].begin(); it!=G[node].end(); it++)
    {
        if(!viz[*it])
        {
            DF(*it);

            best[node] = maxw(best[node],best[node]+best[*it]);
            maxv = maxw(maxv,best[node]);
        }
    }
}

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

    maxv = -20000;
    scanf("%d",&n);
    for(int i=1; i<=n;i++)
    {
        scanf("%d",&v[i]);
        best[i]=v[i];
        if( maxv < v[i])
         maxv = v[i];
    }
     int x,y;
    while(1)
    {
        scanf("%d %d",&x,&y);
        if(feof(stdin))
           break;
        G[x].push_back(y);
        G[y].push_back(x);
    }

      for(int i=1;i<=n; i++)
        if(!viz[i])
          DF(i);
      printf("%d",maxv);
}