goodinet   2년 전

이 문제를 완전탐색의 최적해를 구하면서 가지치기를 하면서 시간을 줄이려 했으나 역시나 시간초과가 발생하네요...ㅠㅠㅠ

같은 함수를 2번 이용하는 데 변수초기화하고 그런 과정이 많아 지저분해서 코드의 일부분만 첨부합니다.

vector<pair<int, vector<int> > > t; 에서,

t[i].first는 i번째 트롤픽을 가지고 있는 플레이어 수

t[i].second는 i번째 트롤픽을 가지고 있는 플레이어 번호입니다.


각 트롤픽을 할 수 있는 플레이어를 저장 해놓고,

각 트롤픽을 할 수 있는 플레이어가 적은 순서로 소트하고, (이것도 시간을 줄일 것이라 생각되서요)

그 트롤픽에서 안고르거나, 한 명을 고르면서 모든 경우에 대해 수행 하는데

약간의 가지치기를 통해 시간을 줄여보려 했으나 줄여지지 않네요ㅠ


이렇게 풀기는 힘드려나요? 어떻게 생각해야 좀 더 빠르게 작동하는 알고리즘이 나오게 될까요?..

wonmo   2년 전

n이 300이고 m또한 300이고 k1,2가 500이라 완전탐색은 너무 많은 시간이 걸릴것같아요 ㅠ

이분매칭을 이용해서 팀1과 팀2의 최대 매칭을 구한뒤 팀1의 최대매칭이 더 적다면 승급하는 알고리즘으로 풀면 시간초과 안날거에요

goodinet   2년 전

감사합니다!!!!!!

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