[백준] 3267 - TWO (c++)

https://www.acmicpc.net/problem/3267

 Croatian Highschool Competitions in Informatics > 2002 > National Competition #2 - Seniors 3번

 

문제 요약

청소부 두명이 트리를 청소하려고 한다. 주어진 트리에서 모든 간선을 한 번 이상 거치면 청소를 마쳤다고 한다. 트리와 청소부의 시작 위치가 주어질 때 청소부가 청소를 마치는데 걸리는 최소 시간을 구해라.

 

풀이 (M+N)

• DFS

한 번만 거치는 간선이 있고 왕복을 해야 하는 간선이 있을 것이다. 한 번만 거치는 길이가 클 수록 좋기 때문에 트리의 지름을 구해준다. 지름에 포함되지 않는 간선은 모두 왕복해야 하기 때문에 답은 ((가중치 총합-지름)*2+지름)이 된다. 시작점이 지름에 포함되지 않아도 지름에 포함되는 정점까지 가는 비용이 왕복하는 비용과 같기 때문에 풀이가 항상 성립된다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+1;

int n,s, mx,mi,sum;
vector<array<int,2>> adj[N];

void dfs(int u,int p,int d) {
    for(auto v:adj[u]) if(v[0]!=p) 
        dfs(v[0],u,d+v[1]);
    if(mx<d)
        mx=d,mi=u;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin>>n>>s;
    for(int i=1,u,v,c;i<n;i++)
        cin>>u>>v>>c,adj[u].push_back({v,c}),adj[v].push_back({u,c}),sum+=c;
    
    dfs(1,0,0);
    dfs(mi,0,0);
    cout<<(sum-mx)*2+mx;
}