글 읽기 - 이러한 문제들은 어떤 방식으로 풀어야 되나요??

dfwdf77 7년 전 0

이런 방식의 문제들은 어떻게 풀어야 하는지 모르겠네요... ㅠㅠ

jseo 7년 전 0

문제 변역이 좀 이상하네요...

힌트를 드리자면 일단 https://www.acmicpc.net/proble... 를 풀어보세요.

dfwdf77 7년 전 0

이 문제가 트리의 지름과 비슷하나요??

트리의 지름은 그냥 루트노드에서 트리의 지름 구하는거 아닌가요??

이 문제는 모든 정점을 다 돌아다니면서 거리 구하는거 아닌가요??

잘 모르겠네요 ㅠㅠ

jseo 7년 전 0

문제 번역이 이상해서 문제를 잘못 이해하고 계실 가능성이 있을수도 있어요

dfwdf77 7년 전 0

말씀하신 대로 트리의 지름으로 풀려고 하는데

제가 푼 방식이 트리의 지름을 구하고

나머지 안간 간선은 다 더한 다음 곱하기 2배를 하여서

답:트리의 지름+(나머지 안간 간선*2)이렇게 풀었는데

틀렸다고 나오는데 제가 푸는 방식이 맞나요???

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

vector<pair<int,int> > adj[10001];
int x,res,idx,cnt,hi;
int dist[10001];

void f(int h, int p,int d) {
	cnt++;
    if (d > res) res = d, idx = h;
	if(hi<cnt)
		hi=cnt;
	for (int i=0;i<adj[h].size();i++) 
		{
			int it1=adj[h][i].first;
			int it2=adj[h][i].second;
			if (it1^p)
				{
					//chk[it1]=1;
					f(it1, h, d + it2);
				}
		}

	cnt--;
}

void f1(int h, int p,int d) {

    if (d > res) res = d, idx = h;

	for (int i=0;i<adj[h].size();i++) 
		{
			int it1=adj[h][i].first;
			int it2=adj[h][i].second;
			if (it1^p)
				{
					//chk[it1]=1;
					f(it1, h, d + it2);
					
				}
		}

}

int y;
int main()
{
	scanf("%d %d",&x,&y);

	for(int i=1;i<x;i++)
	{
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		dist[i]=c;
		adj[a].push_back(make_pair(b,c));
		adj[b].push_back(make_pair(a,c));
	}
	sort(dist,dist+x);
	
	f1(y,0,0);
	f(idx,0,0);
////////////////////////////트리의 지름을 구한것 res가 트리의 지름/////////////
	for(int i=1;i<=x-hi;i++)
		res+=dist[i]*2;
    //////////////////// 나머지 안간 간선 곱하기 2배해서 res에 더함///////////////
	printf("%d",res);
	scanf("%d",&x);
	return 0;


}

jseo 7년 전 0

네 답은 그게 맞습니다.

다르게 말하면 모든 간선 합 * 2 - 트리 지름이죠.

구현에 문제가 있는것 같네요.

dfwdf77 7년 전 0

아 감사합니다 다시 고쳐볼게요 ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이러한 문제들은 어떤 방식으로 풀어야 되나요??

dfwdf77 7년 전 0

jseo 7년 전 0

dfwdf77 7년 전 0

jseo 7년 전 0

dfwdf77 7년 전 0

jseo 7년 전 0

dfwdf77 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말