글 읽기 - 오류 부분을 모르겠습니다.

heroswift15 5년 전 0

오류 부분을 모르겠습니다.

이분 매칭을 이용하엿습니다.

#include<stdio.h>
#include<string.h>

int map[201][201];
int visit[201];
int d[201];

int N,M,S;
int ptr;


int dfs(int x)
{
	ptr=0;
	while(map[x][ptr])
	{
		int t=map[x][ptr];

			if(visit[t])
			{
				ptr++;
				continue;
			}
			visit[t]=1;

			if(d[t]==0 || dfs( d[t]) )
			{
				d[t]=x;
				return 1;
			}
			ptr++;
	}
return 0;
}



int main()
{
int i,j;
	scanf("%d%d",&N,&M);

	for(i=1;i<=N;i++)
	{
		ptr=0;
		scanf("%d",&S);
		for(j=0;j<S;j++)
		{
			int t;
			scanf("%d",&t);
			map[i][j]=t;
		}
	}


int cnt=0;
for(i=1;i<=N;i++)
{
	memset(visit, 0, sizeof(visit));

	if(dfs(i))
		cnt++;


}


printf("%d",cnt);



/*
	for(i=1;i<=N;i++)
	{
		ptr=0;
		while(map[i][ptr])
		{
			printf("%d ",map[i][ptr]);
			ptr++;
		}

	puts("");
	}
*/


return 0;
}

heroswift15 5년 전 0

실화인가 .c로 구현 하기 진짜 조금 많이 내가 모자른건 지 모르겟지만. 기모찌가 와루이...ㅠㅠㅠㅠㅠㅠㅠㅠㅠ

수정 사항은 아래와 같습니다.

#include<stdio.h>
#include<string.h>

int map[201][201]={0,};
int visit[201]={0,};
int d[201]={0,};

int N,M,S;
int ptr;


int dfs(int x)
{
	ptr=0;

	while(map[x][ptr]>0)
	{
		int t = map[x][ptr];

			if(visit[t]==1)
			{
				ptr++;
				continue;
			}

			visit[t]=1;
			int k=ptr;
			if(d[t]==0 || dfs(d[t]) )
			{
				d[t]=x;
				return 1;
			}

			ptr=k+1;
	}
return 0;
}



int main()
{
int i,j;
	scanf("%d%d",&N,&M);

	for(i=1;i<=N;i++)
	{
		ptr=0;
		scanf("%d",&S);
		for(j=0;j<S;j++)
		{
			int t;
			scanf("%d",&t);
			map[i][j]=t;
		}
	}


int cnt=0;
for(i=1;i<=N;i++)
{
	memset(visit, 0, sizeof(visit));

	if(dfs(i))
		cnt++;
}


printf("%d",cnt);







return 0;
}

heroswift15 5년 전 0

k 를 사용하여 기존에 어디 까지 탐색 해주엇는지 기억 장치를 주었습니다.

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

문제

문제

출처

ICPC

오류 부분을 모르겠습니다.

heroswift15 5년 전 0

heroswift15 5년 전 0

heroswift15 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말