hdu4171 Paper Route 树的性质+DFS

题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=4171

题意：

有n+1个点，这n+1个点由n条边相连，且保证连通。然后给出各个点到出口的距离，要求从0点出发，遍历完n个点后立刻从出口出去。求最少时间。

首先，要读懂题意，在遍历过程中不能以校园作为中转。。当然这是废话了

然后我们很容易知道对于n+1个点，并且有n个边相连的连通图肯定是一颗树

对于树，我们应该熟悉这样一条性质：

从跟节点出发遍历一颗树的所有节点再回到跟节点的花费为一定为他的所有的权值之和的2倍

所以我们可以把出发点0看做根节点，然后通过dfs求出各个点到根节点的距离step[i]。

然后我们就可以求出假设它遍历完后回到根节点的总距离sum，然后对于点i，它花费的实际值s=sum-step[i]+out[i]，枚举找到最小的即可。

代码：

 1 #include<iostream>
 2 #include<cstdlib>
 3 #include<cstdio>
 4 #include<cstring>
 5 #define maxn 100100
 6 using namespace std;
 7 long long  d[maxn];
 8 class node
 9 {
10   public:
11   int to;
12   int next;
13   int w;
14 };
15 node edge[maxn*3];
16 int  head[maxn*2];
17 int vis[maxn];
18 int  tol;
19 int  step[maxn];
20 long long sum;
21 int n;
22 void init()
23 {
24     memset(head,-1,sizeof(head));
25     memset(step,0,sizeof(step));
26     memset(vis,0,sizeof(vis));
27     tol=0;
28     sum=0;
29 }
30 void add(int u,int v,int w)
31 {
32    edge[tol].to=v;
33    edge[tol].w=w;
34    edge[tol].next=head[u];
35    head[u]=tol++;
36 }
37 void dfs(int u)
38 {
39    vis[u]=1;
40    for(int i=head[u];i!=-1;i=edge[i].next)
41    {
42 
43       int v=edge[i].to;
44       if(vis[v]==1) continue;
45       step[v]=step[u]+ edge[i].w;
46       sum+=edge[i].w;
47       dfs(v);
48    }
49 }
50 int main()
51 {
52    int u,v,w;
53    while(scanf("%d",&n)!=EOF)
54     {
55        init();
56        for(int i=0;i<=n;i++)
57            scanf("%I64d",&d[i]);
58        for(int i=1;i<=n;i++)
59        {
60          scanf("%d%d%d",&u,&v,&w);
61          add(u,v,w);
62          add(v,u,w);
63          //sum+=w;
64        }
65        //sum*=2;
66        dfs(0);
67        sum*=2;
68        long long  ans=sum+d[0];
69 
70        for(int i=1;i<=n;i++)
71        {
72           ans=min(sum-step[i]+d[i],ans);
73        }
74 
75 
76        printf("%I64d
",ans);
77 
78     }
79 
80     return 0;
81 }

hdu4171 Paper Route 树的性质+DFS

相关推荐