글 읽기 - 이분매칭에서...

petil777 8년 전 0

처음엔 상어의 능력치가 같을 때 서로 잡아먹는다고 가정하고 나중에 서로 잡아먹은 수만큼 다시 상어를 살려주는 방식으로 했었는데 그렇게 하면 서로 잡아먹어서 잡아먹는 횟수를 의미없이 한번더 소모하게되어 다른 상어를 잡아먹을 수 있는 기회가 사라져서 틀린다고 생각했습니다(사실 이렇게 했는데 틀렸구요 ㅠ.ㅠ)

그래서 능력치가 완전히 같을 때는 작은 번호의 상어가 더 우위를 가진다고 보았고 그 경우엔 큰 번호의 상어가 불리한 위치가 되므로 최대한 많은 상어가 먹히기 위해선 큰 번호부터 매칭을 시도해야 한다고 생각했습니다(그래야 먹고 먹히는 관계 수가 늘어나기 때문에)...그런데도 틀리네요 ㅠㅠ 혹시 제 코드에 또다른 틀린점이나 이 논리가 잘못됐다면 바로 잡아주세요..

#include <cstdio>
#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;


int n;
//i가 j를 먹을 수 있으면 1
vector <int> CanEat[1001], visited, bmatch;
typedef struct _shark{
	long long int size, speed, intel;
}shark;

bool dfs(int now, vector <int>& bmatch, vector <int>& visited)
{
	if (visited[now]) return false;
	visited[now] = 1;
	for (int i = CanEat[now].size()-1; i>=0; i--)
	{
		int next = CanEat[now][i];
		if (bmatch[next] == -1 || dfs(bmatch[next], bmatch, visited))
		{
			bmatch[next] = now;
			//bmatch[now] = next;
			return true;
		}

	}
	return false;
}

int matching()
{
	int ret = 0;
	bmatch = vector<int>(n + 1, -1);
	for (int i = n; i >=1; i--)//능력치 같을 때 큰 인덱스가 불리한 위치이므로 먼저 매칭시킨다.
	{
		visited = vector<int>(n + 1, 0);
		if (dfs(i, bmatch, visited))
			ret++;
		visited[i] = 0;//한번 더 매칭할꺼라 시작만 체크해제
		//한번 더 매칭!
		if (dfs(i, bmatch, visited))
			ret++;
	}
	return ret;
}

int main(){
	scanf("%d", &n);
	shark s[1001];

	for (int i = 1; i <= n; i++)
	{
		scanf("%lld%lld%lld", &s[i].size, &s[i].speed, &s[i].intel);
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = i + 1; j <= n; j++)
		{
			if (s[i].size == s[j].size && s[i].speed == s[j].speed && s[i].intel == s[j].intel)
				CanEat[i].push_back(j);
			else if (s[i].size >= s[j].size && s[i].speed >= s[j].speed && s[i].intel >= s[j].intel)
				CanEat[i].push_back(j);
			else if (s[i].size <= s[j].size && s[i].speed <= s[j].speed && s[i].intel <= s[j].intel)
				CanEat[j].push_back(i);
		}
	}
	
	printf("%d\n", n-matching());
}

baekjoon 8년 전 0

서로 잡아먹는 경우를 막기 위해서 같은 경우에는 작은 인덱스가 큰 인덱스를 잡아먹는다 또는 그 반대로 처리한 것은 맞습니다. 그리고, 그렇게 그래프를 만든다고 해도 큰 번호가 불리하지는 않습니다. 왜냐하면, 이게 설명하기 조금 어렵긴한데, 간단하게 설명하면 그리디가 아니고 이분매칭이기 때문이지요.

그리고 제출한 방법이 맞는 방법이긴 합니다

petil777 8년 전 0

어느 부분이 잘못되었는지 알았습니다...그런데 dfs로 이분매칭하니까 시간초과나네요...이 방법이 Ford fulkerson으로 알고있는데 bfs로 확대경로찾는 edmonds-karp를 써야하는건가요? 그런데 간선용량이 1인 단순이분매칭의 경우는 dfs로 찾는게 일반적으로 더 빠르다고 들었는데 이 문제는 그렇지 않네요...

단순이분매칭이라면 dfs로 할때 시간복잡도가 어떻게 되나요? 그리고 이 문제같이 단순매칭인데도 dfs로 찾으면 초과난다는 것을 상어가1000마리라는거에서 눈치채야하는 건가요..? 200~300마리정도여야 가능한건지..?

baekjoon 8년 전 0

구현 실수입니다.

560400번 소스에서

visited[i] = 0;를 visited = vector<int>(n + 1, 0);로 바꿔야 합니다.

두 매칭은 서로 독립적인 매칭이기 때문에, visited를 재활용하면 안됩니다.

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

문제

문제

출처

ICPC

이분매칭에서...

petil777 8년 전 0

baekjoon 8년 전 0

petil777 8년 전 0

baekjoon 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말