## live archive 4267 - Finding The Heaviest Path

Do you want to discuss about these problems? Go now!
Users are shared (no need to re-register).

Moderator: Board moderators

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

### live archive 4267 - Finding The Heaviest Path

Could someone help me with the problem??? I always got WA (about 50 times...) ! Could someone help me with my code? please

Code: Select all

``````#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <memory.h>
#define MAX 10010
using namespace std;

int root, N, ansnum;
int ans[MAX], outdeg[MAX], C[MAX], W[MAX], path[MAX];
bool isfind[MAX];

int dp(int now)
{
//a leaf node
if(outdeg[now]==0)
return W[now];

//if is found
if(isfind[now]) return C[now];

//top-down
int i, next, w, best;

{

//if(next==parent)continue;

w = dp(next);

if(i==0 || w>best)
best = w, path[now] = next;
else if(w==best)
path[now] = max(path[now], next);
}

if( adj[now].size()==0 )	best = 0;
C[now] = W[now] + best;

//memorized
isfind[now] = true;
return C[now];
}

int main()
{
//freopen("4267", "r", stdin);

int i, j, k, c, datacase, cost;
scanf("%d", &datacase);

while(datacase--)
{
//clear the data
for(i=0; i<MAX; i++) adj[i].clear();

scanf("%d %d", &N, &root);

//read the tree information
memset(outdeg, 0, sizeof(outdeg));
for(i=0; i<N; i++)
{
scanf("%d %d", &W[i], &j);

//the children of node number i
for(k=0; k<j; k++)
{
scanf("%d", &c);
outdeg[i]++;

}
}

//start to find the path and max-cost path
for(i=0; i<MAX; i++)
isfind[i] = false, C[i] = 0, path[i] = -1;

cost = dp(root);
printf("%d", cost);

//find the path (root to leaf)
ansnum = 0, ans[ansnum++] = root;

while(path[root]!=-1)
{
ans[ansnum++] = path[root];
root = path[root];
}

for(i=0; i<ansnum; i++)
{
if(i%10==0)
printf("\n%d", ans[i]);
else
printf(" %d", ans[i]);
}
putchar('\n');

}
return 0;
}

``````
electron