Problem 2195 检查站点（普通树构造）（Vector）

Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem Description

在山上一共有N个站点需要检查，检查员从山顶出发去各个站点进行检查，各个站点间有且仅有一条通路，检查员下山前往站点时比较轻松，而上山时却需要额外的时间，问最后检查员检查完所有站点时所需要的额外时间最少是多少。

Input

包含多组数据每组数据输入第一行为一个整数N 表示站点个数（1<=N<=100000）,接下去N-1 行每行3个整数 x，y，z(1<=z<=10000) 检查站x为检查站y的父节点，x,y之间有一条通路，从y到x需要额外z的时间。（父节点在子节点上方，山顶固定标号为1）

Output

输出一行一个整数表示最少需要花费的额外时间。

Sample Input

61 2 12 4 11 3 13 5 13 6 1

Sample Output

Source

福州大学第十二届程序设计竞赛

题目解析：
本题题意相对简单，而且转化模型的时候其实就是找出一条最长的路径，然后再将所有边的权值相加减掉该部分，为什么这样？因为只有最后走的路程才不用上山，这样的话也就没有什么时间的消耗，至于其他的，只要想遍历完全部就必须有个回溯上山的过程，所以抽象一下就是查找最长路径了。

这里有必要先说一下关于Vector，因为好久已经没有用过Vectoer了，今天也是因为这个东西走了还多弯路（用的是Vector的数组），再多次使用的时候没有Clear一下，所以一直是WR的

这里也让我深刻的认识到Vector的真正的用法和存储机制，为什么要用Vector这种数据结构，这是因为这道题并不是图，而是一个没有规则的树，这样的话开数组不太容易，所以用Vector就相当于动态开辟了，这样存储起来就方便多了
另外注意的是在存储的时候从数组的什么位置开始储存也是有一定技巧的，比如一般的从0或者是从1存储的模式，这里一定要注意下标和PUSH存储的节点信息的一致性，否则必然出错。。。

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdio>
#define  INF 0x3f3f3f3
using namespace std;
vector<int> G[100005];
vector<int> E[100005];
int d[100005];

void dfs(int u){
    int size=G[u].size();
    for(int i=0;i<size;i++){
        int v=G[u][i];
            d[v]=d[u]+E[u][i];
            dfs(v);
    }
}
int main(){
    int n;
	while(cin>>n){
		for(int i=0;i<=n;i++){//由于多组测试数据，所以必须清除一下
		 G[i].clear();	
		 E[i].clear();
		}
	    int SUM=0;
	    int u,v,w;
	    for(int i=0;i<n-1;i++){
	        scanf("%d%d%d",&u,&v,&w);
	        G[u].push_back(v);
	        E[u].push_back(w);
	        SUM+=w;
	    } 
	    d[1]=0;
	    dfs(1);
	    
	    int ans=-1;
	    for(int i=1;i<=n;i++)
	        if(d[i]>ans )
	            ans=d[i]; 
	    cout<<SUM-ans<<endl; 
    		
	}
}

其实本题相对来说比较简单，因为固定了起始位置，只是抽象的时候稍微拐了一点弯，还有一类没有固定其实位置的，相对来说比较困难，需要进行两次的深搜，详情网址：http://lx.lanqiao.org/problem.page?gpid=T32