10308 - Roads in the North

[cpp] 
描述：無根樹題目，實際上就是找一條關鍵路也就是最長路，用dp做 
#include <cstdio>  
#include <cstring>  
#include <vector>  
using namespace std; 
typedef struct 
{ 
    int x,y; 
} Pair; 
vector <Pair> v[10010]; 
int dp[10010],sum; 
bool vis[10010]; 
void dfs(int cur) 
{ 
    int sec=0; 
    vis[cur]=1; 
    int len=v[cur].size(); 
    dp[cur]=0; 
    for(int i=0; i<len; ++i) 
    { 
        int b=v[cur][i].x,c=v[cur][i].y; 
        if(!vis[b]) 
        { 
            dfs(b); 
            if(dp[cur]<dp[b]+c) 
            { 
                sec=dp[cur]; 
                dp[cur]=dp[b]+c; 
            } 
            else if(sec<dp[b]+c) sec=dp[b]+c; 
        } 
    } 
    if(sum<dp[cur]+sec) sum=dp[cur]+sec; 
} 
int main() 
{ 
    int flag=0,count=0; 
    //freopen("a.txt","r",stdin);  
    while(!count) 
    { 
        char s[1010]; 
        flag=sum=0; 
        for(int i=0; i<=10000; ++i) v[i].clear(); 
        while(1) 
        { 
            if(!gets(s)) 
            { 
                count=1; 
                break; 
            } 
            if(!flag&&s[0]==0) 
            { 
                if(!gets(s)) count=1; 
                break; 
            } 
            if(flag&&s[0]==0) break; 
            flag=1; 
            int a,b,c; 
            sscanf(s,"%d%d%d",&a,&b,&c); 
            Pair p; 
            p.x=b,p.y=c; 
            v[a].push_back(p); 
            p.x=a; 
            v[b].push_back(p); 
            vis[a]=vis[b]=0; 
        } 
        dfs(1); 
        printf("%d\n",sum); 
    } 
    return 0; 
}