[BOJ/C++] 1033 칵테일

N-1개의 비율로 N개의 재료와 관련된 전체 비율을 알아낼 수 있습니다.

이를 그래프 관점으로 보면 사이클이 없는 트리 구조로 볼 수 있습니다.

먼저 비율을 같은 기준으로 변환하여 각 재료의 실제 양을 구하기 위해 비율의 최소공배수를 구해야합니다.

입력을 예시로 들면 1, 3, 5, 7의 최소공배수 즉 105 입니다.

임의의 시작 노드를 최소공배수로 업데이트 하고 각 재료들을 비율 계산을 통해 업데이트하면 됩니다.

즉, 최소공배수와 BFS/DFS를 이용하여 문제를 해결할 수 있습니다.

문제에서는 재료의 질량 합이 최소가 되어야 하므로 각 재료를 최대공약수로 나누어주면 됩니다.

int 사용시 overflow가 발생할 수 있습니다

비율을 맞추는 과정에서 최소공배수를 구해야하고 계속 곱셈을 하다보면 int의 범위를 벗어날 수 있습니다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>

using namespace std;

using int32 = long;
using int64 = long long;

static vector<int64> result;
static vector < vector<tuple<int, int, int>>> v;
static int64 lcm=1;

int64 gcd(int64 a, int64 b);
void BFS(int node);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    cin >> N;

    v = vector<vector<tuple<int, int, int>>>(N);
    result = vector<int64>(N, 0);

    for(int i=0; i<N-1; i++)
    {
        int a, b, p, q;
        cin >> a >> b >> p >> q;
        v[a].emplace_back(b, p, q);
        v[b].emplace_back(a, q, p);
        lcm *= p * q / gcd(p, q);
    }

    BFS(0);

    int64 mgcd = result[0];
    for (int i = 1; i < N; i++)
        mgcd = gcd(mgcd, result[i]);

    for (int i = 0; i < N; i++)
        cout << result[i]/mgcd << " ";

    return 0;
}

int64 gcd(int64 a, int64 b)
{
    if (b == 0)
        return a;
    else
		return gcd(b, a % b);
}

void BFS(int node)
{
    queue<int> q;

    q.push(node);
    result[node] = lcm;

    while(!q.empty())
    {
        int cur = q.front();
        q.pop();

        for(auto next : v[cur])
        {
            if (result[get<0>(next)]) continue;

        	result[get<0>(next)] = result[cur] * get<2>(next) / get<1>(next);
        	q.push(get<0>(next));
	        
        }

    }
}