[백준/BOJ] 백준 12784번 : 인하니카 공화국

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

12784번: 인하니카 공화국

1번 노드가 루트인 트리를 만들고 리프 노드와 연결을 끊는 최소 비용을 구해서 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int tc;
int n, m;
vector<pair<int, int>> adj[1001]; //(다이너마이트 수, 목적지)
vector<int> maked(1001);
vector<pair<int, int>> children[1001]; //(다이너마이트 수, 자식노드)

void Pre()
{
	for (int i = 0; i < 1001; i++)
	{
		adj[i].clear();
		maked[i] = 0;
		children[i].clear();
	}
}

//here노드가 루트인 트리 만들기
void MakeTree(int here)
{
	maked[here] = 1;

	for (int i = 0; i < adj[here].size(); i++)
	{
		int there = adj[here][i].second;
		int this_cost = adj[here][i].first;

		if (maked[there] == 0)
		{
			children[here].push_back(make_pair(this_cost, there));
			MakeTree(there);
		}
	}
}

//here이 루트인 서브트리에서 리프노드와 연결을 끝는 최소 비용을 구한다
int Solve(int here)
{
	//here이 리프노드일때
	if (children[here].size() == 0)
		return 987654321;

	int ret = 0;

	for (int i = 0; i < children[here].size(); i++)
	{
		int there = children[here][i].second;
		int this_cost = children[here][i].first;

		ret += min(this_cost, Solve(there));
	}

	return ret;
}

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

	cin >> tc;

	for (int t = 0; t < tc; t++)
	{
		Pre();

		cin >> n >> m;

		if (n == 1)
		{
			cout << 0 << "\n";
			continue;
		}

		for (int i = 0; i < m; i++)
		{
			int u, v, d;

			cin >> u >> v >> d;

			adj[u].push_back(make_pair(d, v));
			adj[v].push_back(make_pair(d, u));
		}
		MakeTree(1);

		cout << Solve(1) << "\n";
	}

	return 0;
}