[BOJ 12784] 인하니카 공화국

12784번: 인하니카 공화국

 

이 문제와 정확히 일치하는 문제를 GCC 출제 큐에 push하고 나서 반나절 뒤에 트리 디피 문제를 찾아 풀다가 우연히 발견했다. AC를 받기 전까지 제발 내 착각이기를 빌었다.. 흔한 유형이라 비슷한 문제가 있을 거라고 생각하기는 했지만, 아쉬운 것은 어쩔 수 없다.

 

풀이

 

루트와 리프를 연결하는 경로가 없도록 만들 때, 자르는 간선의 가중치의 합이 최소가 되게 하는 문제다.

이는 dfs를 돌면서 트리의 정점에 대한 dp를 해결하면 된다.

$dp[u]=\sum min(val,dp[v])$ 이고, $v$ 가 리프일 때를 따로 처리해줘야 한다.

 

코드

 

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> ad[1001];
int dfs(int u,int p) {
	int ret=0;
	for(auto &[v,d] : ad[u]) if(v^p){
		int k=dfs(v,u);
		ret+=k?min(d,k):d;
	}
	return ret;
}
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	int tc; cin >> tc;
	while(tc--){
		int n,m; cin >> n >> m;
		for(int i=1;i<=n;i++) ad[i].clear();
		while(m--){
			int u,v,d; cin >> u >> v >> d;
			ad[u].push_back({v,d});
			ad[v].push_back({u,d});
		}
		cout << dfs(1,0) << '\n';
	}
}