글 읽기 - 반례를 찾았는데 어떻게 해결할지 모르겠습니다..

cdt416z 2년 전 0

22 23 1

1 2

2 3

2 4

2 5

2 6

6 7

6 8

6 22

1 16

16 17

16 18

16 19

16 20

16 21

21 22

1 9

9 10

9 11

9 12

9 13

13 14

13 15

13 22

1과 16이 아니라 16과 21이 연결되어야하는데 제 코드로는 1과 16이 연결됩니다..

알고리즘이 완전 잘못된걸까요?

/*
백준 2255
1. 루트에 연결 된 노드들의 차수 (낮은 순)
2. 다음 탐색 노드의 차수 (낮은 순)
반례를 찾긴 찾았음
1. 부모랑 비교 했을 때, 갈아치우는게 이득이라면 갈아치운다 => 여기서 오류가 발생할 수도 있다
2. 일단 알고리즘 자체가 잘못되긴 한거니까 알고리즘을 뜯어고친다?
*/
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, n) for(int i = 1; i <= n; i++)
#include <iostream>
#include <queue>
#include <vector>
#include <tuple>

using namespace std;

typedef tuple<int, int, int, int> ti;
int N, M, R;
long long res = 0;
int degree[1001];
int parent[1001];
bool visited[1001];
vector<int> map[1001];
priority_queue<ti, vector<ti>, greater<>> pq;

void prim(){
	visited[R] = true;
	for(auto l : map[R]){
		pq.push({degree[R], degree[l], R, l});
	}
	while(!pq.empty()){
		auto [deg, degNext, here, next] = pq.top();
		pq.pop();
		if(visited[next]) continue;
		visited[next] = true;
		parent[next] = here;
		res += deg;
		cout << here << " " << next << '\n';
		for(auto l : map[next]){
			if(visited[l]) continue;
			pq.push({degree[next], degree[l], next, l});
		}
	}
}

int main() {
   ios::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);
   cin >> N >> M >> R;
   rep(i, M) {
      int a, b;
      cin >> a >> b;
      map[a].push_back(b);
      map[b].push_back(a);
      degree[a]++;
      degree[b]++;
   }
   REP(i, N) parent[i] = i;
   prim();
	cout << res;
   return 0;
}

/*
22 23 1
1 2
2 3
2 4
2 5
2 6
6 7
6 8
6 22
1 16
16 17
16 18
16 19
16 20
16 21
21 22
1 9
9 10
9 11
9 12
9 13
13 14
13 15
13 22
*/

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

문제

문제

출처

ICPC

반례를 찾았는데 어떻게 해결할지 모르겠습니다..

cdt416z 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말