글 읽기 - 반례좀 찾아주세요...ㅠㅠ

jekim1116 4년 전 0

이전에 최소비용 찾는 부분을 완전탐색으로 구현했을때 맞았고, 그 맞은 코드를 가지고 MST부분만 바꾼 것 뿐인데...

다른글에 있던 반례까지 다 돌려보고 MST부분 코드도 뚫어지게 봤는데 도대체 뭐가 문젠지 못찾겠네요...ㅠ

도와주세요!!!!

#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
#pragma warning(disable:4996)
using namespace std;
int map[11][11], N, M, ptr = 0, dp[7][7], visited[7];
int dx[] = { -1,0,0,1 };
int dy[] = { 0,-1,1,0 };
struct Node {
	int x;
	int y;
	int d;
	int len;
};
queue<Node> q[7];

void devideIsland() {
	queue<pair<int, int> > qq;
	int x, y, a, b;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (map[i][j] == -1) {
				qq.push(make_pair(i, j));
				q[++ptr].push({ i,j,-1,0 });
				map[i][j] = ptr;
				while (!qq.empty()) {
					x = qq.front().first;
					y = qq.front().second;
					qq.pop();
					for (int k = 0; k < 4; k++) {
						a = x + dx[k]; b = y + dy[k];
						if (a<1 || b<1 || a>N || b>M) continue;
						if (map[a][b] == -1) {
							map[a][b] = ptr;
							qq.push(make_pair(a, b));
							q[ptr].push({ a,b,-1,0 });
						}
					}
				}
			}
		}
	}
}
void spread(int idx, int x, int y, int k, int len) {
	int a, b;
	a = x + dx[k]; b = y + dy[k];
	if (a<1 || b<1 || a>N || b>M) return;
	if (map[a][b] == idx) return;
	if (map[a][b] > 0) {
		if (len < 2) return;
		if (dp[idx][map[a][b]] == 0) dp[idx][map[a][b]] = len;
		else dp[idx][map[a][b]] = dp[map[a][b]][idx] = min(dp[idx][map[a][b]], len);
	}
	else if (map[a][b] == 0) q[idx].push({ a,b,k,len + 1 });
}
void BFS(int idx) { // idx : 섬의 번호
	int x, y, d, len;
	while (!q[idx].empty()) {
		x = q[idx].front().x;
		y = q[idx].front().y;
		d = q[idx].front().d;
		len = q[idx].front().len;
		q[idx].pop();
		if (d == -1) {
			for (int k = 0; k < 4; k++) spread(idx, x, y, k, len);
		}
		else spread(idx, x, y, d, len);
	}
}
struct Line {
	int x, y, w;
	bool operator<(Line& l) {
		return w < l.w;
	}
};
vector<Line> v;
int root[7];
int find(int idx) {
	if (root[idx] == idx) return idx;
	return root[idx] = find(root[idx]);
}
void union_root(int a, int b) {
	root[a] = b;
}
int mst(){
	int x, y, res = 0;
	for (int i = 1; i <= ptr; i++) 
		for (int j = i + 1; j <= ptr; j++) 
			if (dp[i][j]>=2) v.push_back({ i,j,dp[i][j] });

	sort(v.begin(), v.end()); // 간선들 정렬
	for (int i = 1; i <= ptr; i++) root[i] = i; // 각 섬의 루트는 자기자신으로 초기화 
	for (int i = 0; i < v.size(); i++) {
		x = find(v[i].x);
		y = find(v[i].y);
		if (x == y) continue;
		union_root(x, y);
		res += v[i].w;
	}
	int tmp = find(1);
	for (int i = 2; i <= ptr; i++) if (tmp != find(i)) return -1;
	return res;
}
int main()
{
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j]) map[i][j] = -1;
		}
	}
	devideIsland();
	for (int i = 1; i < ptr; i++) BFS(i);
	printf("%d\n", mst());
}

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

문제

문제

출처

ICPC

반례좀 찾아주세요...ㅠㅠ

jekim1116 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말