kkw564   2년 전

최대 유량을 잡고, 한번더 유량을 흘려보내며 S->T로 유량이 흐르는지 확인하는 과정으로 답을 구했습니다.

이때 

//if (next == T)
// break;이 과정이 주석이어야만 AC이고 주석이 아니면 WA인데 왜 그런건가요..? 도저히 이해가 안되네요

kks227   2년 전

주석이 두 군데 있는데 둘 다 주석처리되어야 정답이고 둘 다 주석처리가 되어있지 않으면 오답이란 말씀이신가요?

kks227   2년 전

두 번째 주석 부분이 문제인 것 같네요. 어떤 간선을 잡고 그 시작점에서 유량을 흘려 반대편 끝점에 도달할 수 있으면 중요한 간선이 아니라는 것이 코드의 구조인데...두 번째 주석이 풀린다면 c[cur][next] - f[cur][next] > 0 이 구문이 거짓이어도 반복문을 나와버리네요.

1
4 4
1 2 1
2 4 1
2 3 1
3 4 1

이 케이스를 넣어보시면, 정답은 1이지만 주석이 해제되면 2가 나옵니다.

간선 (1, 2)만이 유일한 중요한 간선인데, 간선 (2, 4)를 체크하는 중에 아마도 비어있을 2->3->4 증가경로가 존재하겠지만 그냥 간선 (2, 4)가 이미 차있다는 이유로 나와버립니다.

1
4 4
1 2 1
2 3 1
3 4 1
2 4 1

실제로 이렇게 간선 순서만 바꿔서 (2, 4)를 맨 마지막 위치로 옮기면 답이 1이 나오는 걸 확인하실 수 있습니다. 이는 간선 순서상 2->3->4 경로를 먼저 체크하게 되고 증가 경로를 찾기 때문에 일어나는 일이죠.

kkw564   2년 전

감사합니다!! 와.. 명쾌하네요

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