취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 27730번 문제인 견우와 직녀이다.
문제는 아래 링크를 확인하자.

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

오작교를 이을 \(E\)의 정점 번호를 \(e\), \(W\)의 정점 번호를 \(w\)라 하자. 이 때 \(E\)와 \(W\)의 정점 쌍 사이의 거리의 총합을 (1) \(E\)의 각 정점으로부터 \(e\)로 이동을 \(W\)의 정점의 개수만큼, (2) \(e\)에서 \(w\)로 이동을 \(E\)와 \(W\)의 정점 쌍의 개수만큼, , (3) \(w\)로부터 \(W\)의 각 정점으로 이동을 \(E\)의 정점의 개수만큼 하는 것으로 나누어 생각해보자. 이 중 \(E\)와 \(W\)의 크기는 주어지는 값으로 고정되므로, 주어진 트리에서 모든 정점까지의 거리의 총합이 가장 작은 정점을 찾을 수 있다면 문제를 해결할 수 있게 된다.

트리에서 모든 정점까지의 거리의 총합이 가장 작은 정점을 찾아 문제를 해결하자. 이는 DP를 이용해 어렵지 않게 구할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;

ll N;
vector<pair<int, ll>> G[100001];
ll streecnt[100001];
ll dp[100001];
ll dp2[100001];
void func(int cur, int par) {
    ll &val = dp[cur] = 0;
    streecnt[cur] = 1;
    for (auto &p:G[cur]) {
        if (p.first == par) continue;
        func(p.first, cur);
        val += streecnt[p.first] * p.second + dp[p.first];
        streecnt[cur] += streecnt[p.first];
    }
}

void func2(int cur, int par, ll pval) {
    if (!par) dp2[cur] = dp[cur];
    else {
        dp2[cur] = dp2[par] - streecnt[cur] * pval + (N - streecnt[cur]) * pval;
    }
    for (auto &p:G[cur]) {
        if (p.first == par) continue;
        func2(p.first, cur, p.second);
    }
    
}
ll anode1, aval1, sz1, anode2, aval2, sz2;

void solve(ll &an, ll &av, ll &z) {
    cin >> N; z = N;
    for (int i = 1; i <= N; i++) G[i].clear();
    memset(streecnt, 0, sizeof(streecnt));
    for (int i = 1; i < N; i++) {
        int x, y, w; cin >> x >> y >> w;
        G[x].emplace_back(make_pair(y, w));
        G[y].emplace_back(make_pair(x, w));
    }

    func(1, 0);
    func2(1, 0, 0);
    av = 1000000000000000007LL;
    for (int i = 1; i <= N; i++) {
        if (dp2[i] < av) av = dp2[i], an = i;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    solve(anode1, aval1, sz1);
    solve(anode2, aval2, sz2);
    cout << anode1 << ' ' << anode2 << '\n';
    cout << aval1 * sz2 + aval2 * sz1 + sz1 * sz2;

}