글 읽기 - 흠...뭐가틀린지 모르겠습니다!?

jkb7676 7년 전 0

이제막 네트워크 플로우에 입문한 학생입니다

도저히 뭐가틀린지 모르겠습니다...ㅠㅠ

그리고 제가 작성한 방식이 이분매칭이 맞나요??

#include<stdio.h>
#include<memory.h>
int n;
typedef struct shark1
{
	int a,b,c;	
}s;
	s shark[2001];
	int arr[2001][2001];
	int tracer[2001];
	int visit[2001];
	
int dfs(int k,int cnt)//K 현재 샤크! 
{
	int i,j;
	int a,b,c;
	int a1,b1,c1;
	if(k==n*2+1)
	{cnt--;
		while(cnt!=1)
		{
			arr[tracer[cnt]][tracer[cnt-1]] += 1;
			arr[tracer[cnt-1]][tracer[cnt]] -= 1;
			cnt--;
		}//백 엣지 설정... 어렵달미ㅏㄷㄻ딜더룸ㄷ러ㅏㅝㅣ미ㅏ 
		return 1;
	}
	a = shark[k].a;
	b = shark[k].b;
	c = shark[k].c;
	for(i=1; i<=n*2+1; i++)
	{
		a1 = shark[i].a;
		b1 = shark[i].b;
		c1 = shark[i].c;
		if(k==0||k>i)//출발점이거나 백엣지로 이동할때. 
		{
			if(arr[k][i]>=1&&visit[i]==0)
			{
				visit[i] = 1;
				tracer[cnt] = i;
				if(dfs(i,cnt+1))return 1;
			}
		}
		else
		{
			if(a==a1&&b==b1&&c==c1&&arr[k][i]>=1&&visit[i]==0)//모든 능력치가 같을때 
			{
				arr[i-n][k+n] = 0;//만약 1번상어와 2번상어가 같다면 2->1로 오는경로를 막음! 
				visit[i] = 1;
				tracer[cnt] = i;
				if(dfs(i,cnt+1))return 1;
			}
			else if(a>=a1&&b>=b1&&c>=c1&&arr[k][i]>=1&&visit[i]==0)//잡아먹을수 있을때 
			{
				visit[i] = 1;
				tracer[cnt] = i;
				if(dfs(i,cnt+1))return 1;
			}
		}
	}
	return 0;
}
int main()
{
	int i,j,k;
	int cnt=0;
	scanf("%d",&n);
	for(i=1; i<=n; i++)
	{
		scanf("%d %d %d",&shark[i].a,&shark[i].b,&shark[i].c);
		shark[i+n].a = shark[i].a;
		shark[i+n].b = shark[i].b;
		shark[i+n].c = shark[i].c;
	}
	
	for(i=1; i<=n; i++)arr[0][i] = 2;
	for(i=1; i<=n; i++)
	{
		for(j=1; j<=n; j++)
		{
			if(i==j)continue;
			arr[i][j+n] = 1;
		}
	}
	for(i=n+1; i<=n+n; i++)arr[i][n+n+1] = 1;
	
	while(dfs(0,1))
	{
		cnt++;
		memset(visit,0,sizeof(visit));
	}
	printf("%d",n-cnt);
}

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

문제

문제

출처

ICPC

흠...뭐가틀린지 모르겠습니다!?

jkb7676 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말