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

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

live archive 4267 - Finding The Heaviest Path

Post by f74956227 » Sun Mar 08, 2009 7:46 am

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
		return W[now];

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

	int i, next, w, best;

	for(i=0; i<(int)adj[now].size(); i++)
		next = adj[now][i];


		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;

	isfind[now] = true;
	return C[now];

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

	int i, j, k, c, datacase, cost;
	scanf("%d", &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);


		//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;

			ans[ansnum++] = path[root];
			root = path[root];

		for(i=0; i<ansnum; i++)
				printf("\n%d", ans[i]);
				printf(" %d", ans[i]);

	return 0;


Post Reply

Return to “ACM ICPC Archive Board”