POJ 1849 Two (树的直径)

2016年7月17日 0 作者 CrazyKK

题目链接

题意:一棵树。。然后初始两个推雪机在点s,问如何选择路径使得处理完所有边上的积雪所耗费的汽油最少（走过一条有雪的边和一条没雪的边耗费的汽油一样）

 

思路：很容易想到，我们应该尽可能不走已经被清理过雪了的边，因为这样很浪费。。。这样不难想到应该是和树的直径有关。但是初始的位置是给定的。。。怎么办？突然发现由于是给了两个推雪机。。所以其实相当于。。。只有一个推雪机&我们可以从任意位置开始推雪。。。第二个问题是。。。对于不在直径上的边。。我们怎么算cost?解决办法是读边的时候进行记录。。。然后求直径的时候记录路径。。。对于一条边。。。只要有一个点不在直径上。。。那么这条边的代价就是2倍。。。

1A蛤蛤蛤

 

 

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
 
 
 
/* ***********************************************
Author :111qqz
Created Time :2016年07月17日 星期日 19时04分49秒
File Name :code/poj/1849.cpp
************************************************ */
 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
 
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7;
vector < pi > edge[N];
int n,s;
int lst;
int beg;
int d[N];
bool vis[N];
bool onpath[N];
int path[N];
int ans;
 
struct  Edge
{
    int u,v,w;
 
}e[N];
void init( int n)
{
    for ( int i = 1 ; i <= n ; i++) edge[i].clear();
    ms(path,-1);
    ms(onpath,false);
}
 
void bfs( int s)
{
    ms(d,0);
    ms(vis,false);
    queue<int>q;
    q.push(s);
    vis[s] = true;
 
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
 
        int siz = edge[u].size();
 
        for ( int i = 0 ;i  < siz;  i++)
        {
            int v = edge[u][i].fst;
            int w = edge[u][i].sec;
            if (vis[v]) continue;
            path[v] =  u;
            vis[v] = true;
            d[v] = d[u] + w;
            q.push(v);
        }
    }
 
}
int main()
{
        #ifndef  ONLINE_JUDGE
        freopen("code/in.txt","r",stdin);
  #endif
 
        
        cin>>n>>s;
        init(n);
        for ( int i = 1  ;i <= n-1 ; i ++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            e[i].u = u;
            e[i].v = v;
            e[i].w = w;
            edge[u].push_back(make_pair(v,w));
            edge[v].push_back(make_pair(u,w));
        }
 
        bfs(1);
        int mx = 0 ;
        for ( int i = 1 ; i <= n ; i ++)
            if (d[i]>mx)
            {
                mx = d[i];
                lst = i;
            }
 
        mx = 0 ;
        ms(path,-1);
        bfs(lst);
 
        for ( int i = 1 ; i <= n ; i++)
            if (d[i]>mx)
            {
                mx = d[i];
                beg = i ;
            }
 
        ans = mx;
        int x = beg;
        //cout<<"bfs ok?"<<endl;
        while (x!=-1)
        {
            //cout<<"x:"<<x<<endl;
            onpath[x] = true;
            x = path[x];
        }
        
//        cout<<"ans:"<<ans<<endl;
        for ( int i = 1 ; i <= n-1 ; i++)
        {
            int u = e[i].u;
            int v = e[i].v;
            int w = e[i].w;
            if (onpath[u]&&onpath[v]) continue;
            ans +=w*2;
        }
 
        printf("%d\n",ans);
 
 
        
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}
 
 
 
 

分类目录poj
标签树的直径

关于作者

ex-ACMer@hust，stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人！

提醒
wpDiscuz