글 읽기 - 이분매칭으로 풀었는데 틀렸다고 나옵니다. 반례좀 찾아주세요ㅠㅠ

kelle111 4년 전 0

ㅠㅠ

테스트 케이스는 당연히 잘 돌아가고 있습니다.

왜 틀렸다고 하는건지 ㅠㅠㅠㅠ

고수님 반례좀 찾아주세요... ㅠㅠㅠ

#include<iostream>
#include<vector>
#include<cstring>

using namespace std;
int map[500][500];
int bmatch[500];
int visited[500];
vector<int> adj[500];
bool dfs(int a) {
	if (visited[a] == 1) return false;
	visited[a] = 1;
	for (int b : adj[a]) {
		if (bmatch[b] == 0 || dfs(bmatch[b])) {
			bmatch[b] = a;
			return true;
		}
	}
	return false;
}
int main() {
	int N, M;
	scanf("%d %d", &N, &M);

	for (int i=0; i < M; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		map[a-1][b-1] = 1;
		adj[a - 1].push_back(b - 1);
	}

	int cnt = 0;
	for (int i = 0; i < N; i++) {
		memset(visited, 0, sizeof(visited));
		if (dfs(i)) cnt++;
	}

	printf("%d", cnt);
	return 0;
}

chogahui05 4년 전 1

이런 건 반례를 찾으려고 하면 안 되고, 어디서 잘못될 수 있는지 보아야 해요.

14번째 줄을 보세요.

chogahui05 4년 전 1

bmatch[b] == 0이라는 조건이 만족이 되었을 때

bmatch[b] = a를 넣는 걸로 봐서

a단에서 b로 매칭을 시켰을 때, back을 위한 정보를 담는 게 bmatch인 걸로 보여요. 맞나요?

문제는 bmatch[b] == 0인 경우

kelle님이 짜신 코드에 의하면 0번하고 b하고 매칭이 된 상태라는 건데요. 이게 비어 있는 상태인가요?

지금 0하고 b하고 match 된 상태는 비어 있는 상태도 아니고 kelle님이 정의하신 것에 따르면, vaild한 매칭 상태입니다.

28번째 줄에서 29번째 줄을 보면 보시면 그렇죠? 따라서, bmatch를 -1로 초기화를 해 주시고 14번째 줄을

bmatch[b] == -1이라는 조건으로 수정해 주시면 되겠습니다.

kelle111 4년 전 0

세상에나!!

그렇네요!! 0부터 시작하니까, 0도 valid한 매칭상태가 되는 거군요!!! ㅇㅁㅇ!!

bmatch를 -1로 초기화하고, 말씀하신것처럼 14번째줄을 바꾸니까 "맞았습니다" 가 떳어요!

감사합니다!!

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

문제

문제

출처

ICPC

이분매칭으로 풀었는데 틀렸다고 나옵니다. 반례좀 찾아주세요ㅠㅠ

kelle111 4년 전 0

chogahui05 4년 전 1

chogahui05 4년 전 1

kelle111 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말