글 읽기 - 왜 안될까요

dyddnekt1 4년 전 0

mst 하는 것 마냥 시도해봤는데 안되네요...

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

#define MEMSET(X) (memset(X, 0, sizeof(X)));
#define INIT(X, Y) for(auto &x : X) x = Y;

#define INF ((1 << 30) - 1)
#define MAX_N 16

struct link {
	int i, j, w;
	bool operator() (link l1, link l2){
		return l1.w > l2.w;
	}
};

int N, P;
int C[MAX_N + 1][MAX_N + 1];
int on;

int main(void) {
	scanf("%d", &N);
	MEMSET(C);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &C[i][j]);
		}
	}
	on = 0;
	char temp[MAX_N + 1];
	scanf("%s", temp);
	for(int i = 0; i < N; i++)
		if (temp[i] == 'Y') on = on | (1 << i);

	priority_queue<link, vector<link>, link> q;
	int count = 0;
	for (int i = 1; i <= N; i++) {
		if (!(on & 1 << i - 1)) continue;
		count++;
		for (int j = 1; j <= N; j++) {
			q.push({ i, j, C[i][j] });
		}
	}
	int ans = 0;
	while (!q.empty()) {
		link temp = q.top(); q.pop();
		if (on & 1 << temp.j - 1) continue;
		on = on | (1 << temp.j - 1); count++;
		ans += temp.w;
		for (int i = 1; i <= N; i++) {
			if (on & 1 << i - 1) continue;
			q.push({ temp.j, i, C[temp.j][i] });
		}
	}
	scanf("%d", &P);
	if (count < P) printf("-1\n");
	else printf("%d\n", ans);
}

dyddnekt1 4년 전 0

비싼걸 키면 싼 걸 연달아 킬 수 있는 경우에 틀리는군요

dbfldkfdbgml 3년 전 0

프림 비스무리한 접근으로 이 문제는 풀리지 않습니다. 반드시 모두 다 해봐야 합니다.

그 이유는 싼 간선 + 싼 간선보다 비싼 간선 + 매우 싼 간선의 조합이 있을 수 있기 때문입니다.

꼭 트리를 만들어야 한다는 것이 보장되지 않아요.

그 순간 순간을 그리디하게 접근할 수 없습니다.

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

문제

문제

출처

ICPC

왜 안될까요

dyddnekt1 4년 전 0

dyddnekt1 4년 전 0

dbfldkfdbgml 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말