글 읽기 - 2255 트리 만들기 힌트 부탁 드립니다.

taikun30 4년 전 0

프림 MST 알고리즘으로 접근했는데, 예제 출력은 맞고, 테케가 많지 않아서 반례를 찾기가 어렵네요.

혹 푸신분 있으시면 힌트 또는 접근법 좀 부탁 드리겠습니다.

//BOJ 2255 트리 만들기
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1001	// 1<= N <=1000

int n,m,r;
long long ans;
int Degree[MAXN]; 
bool visited[MAXN];
vector<vector<int>> adj;		//adjcent list for input

struct Edge{
	int node,cost;
	bool operator < (const Edge &ot)const{
		return cost > ot.cost;
	}
};

vector<vector<Edge>> v;

void Prim(int r){
	
	priority_queue<Edge> q;
	
	for(int i=0; i<v[r].size(); i++){
		q.push({v[r][i].node,v[r][i].cost});
	}
	
	visited[r] = true;
	//printf("%d ",r);
	
	ans = 0;
	
	while(!q.empty()){
		Edge now= q.top();q.pop();
		int x = now.node;
		
		if(visited[x]) continue;
		visited[x] = true;
		
		ans += now.cost;
		//printf("%d ",x);
		
		for(int i=0; i<v[x].size();i++){
			Edge next = v[x][i];
			int y = next.node;
		
			if(!visited[y]){
				q.push({y,next.cost});
			}
		}
	}
	//printf("\n");	
}

int main(){

//	freopen("2255.txt","r",stdin);
	scanf("%d %d %d",&n,&m,&r);
	
	memset(Degree,0,sizeof(Degree));
	memset(visited,false,sizeof(visited));
	
	adj.clear(); adj.resize(n+1);
	v.clear(); v.resize(n+1);
	
	for(int i=0; i<m; i++){
		int a,b;
		scanf("%d %d",&a,&b);	

		adj[a].push_back(b);
		adj[b].push_back(a);

		Degree[a]++; Degree[b]++;	
	}
	
	for(int i=1; i<=n; i++){
		for(int j=0; j<adj[i].size(); j++){
			v[i].push_back({adj[i][j],Degree[i]});
		}
	}
	
/*
	for(int i=1; i<=n; i++){
		for(int j=0; j<adj[i].size(); j++){
			printf("{%d %d} ",v[i][j].node, v[i][j].cost);
		}
		printf("\n");
	}		
*/	
	Prim(r);

	printf("%lld\n",ans);
		
	return 0;
} 

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

문제

문제

출처

ICPC

2255 트리 만들기 힌트 부탁 드립니다.

taikun30 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말