글 읽기 - 이 코드 틀린 부분을 찾아주실 분을 찾습니다..(이분매칭)

kkw564 6년 전 0

이제 5일째되는 날입니다.

고민에 고민을해보아도 왜 틀린지 잘모르겠네요

이분매칭 코드 자체는 매번 이분매칭 문제풀때 쓰던 코드이고

아래 while(1)에서 k가 0이 되거나 이분매칭이 하나도 안되었을때 break를 걸고있습니다.

고수님들 제발 도와주십시오ㅠㅠㅠ

#include <iostream>
#include <cstdio>
#include <vector>
#include <memory.h>

using namespace std;

vector<int> adj[1005];
vector<int> aMatch, bMatch;
int visit[1005];
int visitCnt = 1;
int n, m, k;
bool startK;

bool dfs(int a)
{
	if (visit[a] == visitCnt)
		return false;

	visit[a] = visitCnt;

	int len = adj[a].size();
	for (int b = 0; b < len; b++)
	{
		int there = adj[a][b];
		if (bMatch[there] == -1 || dfs(bMatch[there]))
		{
			aMatch[a] = there;
			bMatch[there] = a;

			return true;
		}
	}

	return false;
}

int bipartiteMatch()
{
	int size = 0;
	
	for (int start = 0; start < n; start++)
	{
		visitCnt++;

		if (dfs(start))
		{
			size++;
			if (startK)
			{
				if (k == 0)
					return size;
				k--;
			}
		}
	}

	return size;
}

int main()
{
	scanf("%d %d %d", &n, &m, &k);

	for (int i = 0; i < n; i++)
	{
		int num;
		scanf("%d", &num);

		for (int j = 0; j < num; j++)
		{
			int val;
			scanf("%d", &val);

			adj[i].push_back(val);
		}
	}

	aMatch = vector<int>(n + 5, -1);
	bMatch = vector<int>(n + 5, -1);

	int ans = 0;
	ans += bipartiteMatch();
	startK = true;

	while(1)
	{
		if (k == 0)
			break;

		int get = 0;
		get = bipartiteMatch();

		if (!get)
			break;
		
		ans += get;
	}
	printf("%d\n", ans);

	return 0;
}

ehddml3 6년 전 0

if (k == 0)

return size;

k--;

요 부분의 위쪽을 보시면 k==0일때도 일단 size++이 되는 경우가 생겨서 정답보다 경우에 따라 1큰 값이 나올 수 있을 것 같네용

그리구 bMatch의 사이즈를 조절해보시면 될 것 같습니다.

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

문제

문제

출처

ICPC

이 코드 틀린 부분을 찾아주실 분을 찾습니다..(이분매칭)

kkw564 6년 전 0

ehddml3 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말