petil777   1년 전

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

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

baekjoon   1년 전

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


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

petil777   1년 전

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

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

baekjoon   1년 전

구현 실수입니다.

560400번 소스에서

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

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

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