Uvalive 4267 Finding The Heaviest Path (Regionals 2008 Asia Taipei +DFS結點最大權值路徑)

【題目連結】：​​click here~~​​

【題目大意】：給你一棵樹，在樹上從根節點到葉子結點找一條結點權值最大的路徑，并輸出該條路徑

【思路】：dfs搜尋，遞歸查找權值，遞歸輸出路徑

代碼 ：

/*
* Problem: UVALive 4267
* Running time: 23MS
* Complier: G++
* Author: herongwei
* Create Time: 20:16 2015/10/14
*/
#include <stdio.h>
#include <string.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn=1e4+10;
const int inf=0x3f3f3f3f;
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
int w1[maxn],w2[maxn],a[maxn];
vector<int >G[maxn];
int n,m,len,ans;
int dfs(int root) //遞歸求根節點的權值
{
   int cnt=0;
   for(int i=0; i<G[root].size(); ++i)
   {
       cnt+=dfs(G[root][i]);
    //   cout<<"root= "<<root<<" "<<"i="<<i<<"G[root][i]= "<<" "<<G[root][i]<<endl;
   }
   w1[root]+=cnt;
   //cout<<"cnt= "<<cnt<<endl;
   return w1[root];
}
void dfss(int root)//遞歸求路徑
{
    a[len++]=root;
    ans+=w2[root];
    int ck=-1;
    if(G[root].size()) ck=G[root][0];
    for(int i=0; i<G[root].size(); ++i)
    {
        if(w1[G[root][i]]>w1[ck]) ck=G[root][i];
        else if(w1[G[root][i]]==w1[ck]&&ck<G[root][i])
            ck=G[root][i];
    }
    if(ck<0) return ;
    else dfss(ck);
}
int main()
{
    //freopen("1.txt","r",stdin);
    int t;scanf("%d",&t);
    while(t--)
    {
        len=0,ans=0;
        int n,rt;scanf("%d%d",&n,&rt);
        for(int i=0; i<n; ++i) G[i].clear();
        for(int i=0; i<n; ++i)
        {
            int x,y;scanf("%d%d",&w1[i],&x);
            while(x--)
            {
                scanf("%d",&y);
                G[i].push_back(y);
            }
        }
        for(int i=0; i<n; ++i) w2[i]=w1[i];
        dfs(rt);
      //  cout<<w1[rt]<<endl;
        dfss(rt);
        printf("%d\n",ans);
        for(int i=0; i<len-1; ++i)
        {
            printf("%d",a[i]);
            if(i&&i%10==9) puts("");
            else printf(" ");
        }
        printf("%d\n",a[len-1]);
    }
    return 0;
}