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

(追記) (追記ここまで)

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

11378번 - 열혈강호 4

kkw564 8년 전 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 8년 전 0

if (k == 0)

return size;

k--;

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

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

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC