[7812번] 중앙 트리

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 트리

2. 수학

이 문제의 핵심은 다음과 같다.

하나의 정점을 루트로하여 트리를 만들되, 

dfs로 순회하는 동안 각 정점에서 자신을 포함한 서브 노드의 개수, 간선의 누적 합을 가지고 있어야 한다.

아래 그림은 A정점에서 B, C, D, E로 갈 때 방문하는 총 횟수를 붉은색 선으로 표현하였다.

다음 파란색 선은 B에서 A, C, D, E로 갈 때의 방문 횟수를 표현하였다.

이를 통해 이용 할 수 있는 것은 [[중앙 정점은 모든 정점으로 이르는 비용의 합이 가장 작은 정점]]을 구할 때

즉, 각각의 누적 합을 구할때 A의 누적합을 이용하여 B의 누적합을 구할 수 있다.

B의 누적합은 A-B사이의 간선 횟수 빼고 모두 같다.

따라서 A->B의 A의 누적 합 - (붉은 선 개수 * 가중치) + (파란 선 개수 * 가중치)를 하면 된다.

이를 토대로 B->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

#include <iostream> #include <cstdio> #include <vector> #include <memory.h> #include <limits.h>   #define min(a,b)(a < b ? a : b)   using namespace std;   typedef pair<int, int> pii; typedef long long ll;   vector<pii> vc[10001];   int n; int cnt[10001]; ll sum[10001]; ll ans;   void getTree(int here, int prev) {     cnt[here] = 1;       for (int i = 0; i < vc[here].size(); i++)     {         int next = vc[here][i].first;         int cost = vc[here][i].second;           if (next == prev)             continue;           getTree(next, here);           cnt[here] += cnt[next];         sum[here] += cost * cnt[next] + sum[next];     } }   void getSum(int here, int prev, ll total) {     ans = min(ans, total);       for (int i = 0; i < vc[here].size(); i++)     {         int next = vc[here][i].first;         int cost = vc[here][i].second;           if (next == prev)             continue;           getSum(next, here, total - (cnt[next] * cost) + ((n - cnt[next]) * cost));     } }   int main() {     while(1)     {         scanf("%d", &n);           if (n == 0)             break;           memset(cnt, 0, sizeof(cnt));         memset(sum, 0, sizeof(sum));         ans = LLONG_MAX;           for (int i = 0; i < n; i++)             vc[i].clear();           for (int i = 0; i < n - 1; i++)         {             int from, to, val;             scanf("%d %d %d", &from, &to, &val);               vc[from].push_back(pii(to, val));             vc[to].push_back(pii(from, val));         }           getTree(0, -1);           getSum(0, -1, sum[0]);           printf("%lld\n", ans);     }       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus