sgc109   3달 전

에드몬드카프로 구현해봤는데 20%에서 TLE가 뜹니다.

디닉이나 홉크로프트카프로 하면 1초내에 AC가 뜬다는 댓글은 봤는데 에드몬드카프로 돌릴경우 O(1000^3) 이라 TLE 뜰수밖에없는건가요?

그런데 디닉의 시간복잡도가 O(EV^2)) 이라고 알고있는데 디닉도 TLE가 나야하는거아닌가요? 궁금합니다!

appa

appa   3달 전

디닉을 사용할 필요까지는 없습니다.

appa   3달 전

포드폴커슨, 에드몬드카프 어느 걸로 짜던 AC는 뜨는 걸로 알고있습니다.

lexio   3달 전

이게 N <= 1000이라고 적혀있는데


실제 인풋은 250정도로 알고있습니다

sgc109   3달 전

appa 그렇군요.. 그런데 지금까지 저런 식으로 해서 열혈강호1~4 를 문제없이 AC 받았었는데 왜 이건 TLE가 날까요..? 크게 다르다고 할만한 부분은 72~75 라인의 

꼬리의 꼬리를 무는 잡아먹음(?)을 판별하는 부분과 O(N^2) 로 두 컴포넌트의 간선을 이어주는 부분 뿐인것같은데..

sgc109   3달 전

lexio 그렇군요.. 그럼 실제 인풋이 1000까지 들어간다면 에드몬드카프로는 안되겠죠..?

kks227   3달 전

어...그런데 제가 처음에 이 문제를 풀 때 에드몬드 카프로 풀었는데 맞았던 기억이 납니다. 시간은 엄청 걸리긴 했지만요.

sgc109   3달 전

kks227 그렇군요 그런데 도대체 어디서 시간초과가 나는걸까요.. 소스코드를 아무리봐도 그렇게 시간이 지체될만한곳은 발견하지 못하겠네요ㅠㅠ

kks227   3달 전

혹시 두 상어의 능력치가 완전히 같은 경우를 처리하셨나요? 이때는 서로 잡아먹는 게 가능한데, 실제로 이런 인풋이 들어오는지는 모르겠지만 만약 들어온다면 아주 예상할수없는 온갖 예외를 발생시킬 것 같네요.

sgc109   3달 전

kks227 네 처리해서 전체 상어중 일부 여러마리의 능력치가 같을때도 올바른결과가 나오고 20%까진 맞는데 거기서 시간초과가나네요..

kks227   3달 전

제 예전 코드를 보니까 에드몬트 카프 알고리즘인데 메모리만 많이 썼을 뿐 시간이 0MS 걸렸었네요. 뭔가 다른 이유가 있는 것 같습니다.

sgc109   3달 전

kks227 아 생각해보니 제가 DFS를 써서 포드풀커슨 이라고 봐야할것같은데 혹시 BFS 로 하셔서 AC받으셨나요?

appa   3달 전

cap - flow를 cap으로 해서 다음과 같이 구현해서 일단 시간초과 문제는 해결했습니다.

상어가 서로 먹고 먹힐 수 있는 경우에 대해서 제대로 처리 안해주셨네요.

appa   3달 전

위에서 말한 경우를 처리하면 다음과 같은 소스로 AC를 받을 수 있네요. 0MS가 나옵니당.

sgc109   3달 전

appa 감사합니다. 사실 원본코드의 72~75 라인으로 서로 먹고 먹히는걸 처리해준거였는데 

애초에 잘못된 예외처리코드였을수도 있지만 만약 아니라면 시간초과 문제를 해결한뒤엔 그걸없애서 틀렸습니다가 뜬것같네요!

그런데 속도는 그걸 없애서 시간이 빨라진걸까요? 아니면 cap에서 flow 를 계속 빼주는 연산을 없애준것만으로 속도가 빨라진건가요?

사실 열혈강호의 포드풀커슨 해법 소스코드를 보내주셨을때도 홍준님의 소스와 제 소스가 cap과 flow 를 따로 관리해준것과 증가경로를 두번 순회하며 최소 증가량을 찾아 flow 를 증가시켜주는부분? 빼곤 비슷하다고 생각했는데 항상 속도가 차이가 나길래 cap과 flow 를 따로 계산하지않는것때문에 속도가 꽤 차이가 나는건지 계속 의문이었습니다.. 

appa   3달 전

음... 그것 때문에 속도 차이는 거의 없을 것 같은데 원래 소스에서

if(flow[finish-n][start+n] == 1) {
            flow[start][finish]=1;
            continue;
}
이 부분이 무엇을 뜻하는지 몰라서 그냥 제가 원래 짜던 방법대로 고쳐보았어요 ㅋㅋㅋ

sgc109   3달 전

appa 아 ㅋㅋ 그 부분이 A 그룹에 있는 노드에서 B 그룹의 노드로 여분의 용량이 있어서 갈려고할때 그 B그룹의 노드가 이미 자기를 먹은상태면 먹지못하니까 막아버ㅣ려고 했던거에요! flow 를 1로 해버리거나 cap을 0으로 바꾸는식으로해서.. 근데 그게 시간초과를 야기할지는 좀 긴가민가해서 사실 그부분이 문제인지 다른부분이 문제인지 의문이었거든요..

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