cokcjswo   4년 전

의식의 흐름은 다음과 같습니다.

1. 기존의 종만북 바탕의 네트워크 플로우 작성 -> 어 capacity, flow 배열이 못잡을 정도로 겁나 커지네 구조체로 간선 만들어야겠다.

2. kks님 블로그 참조해서 구조체 edge 기준으로 maxflow 재작성 -> 어 알고보니 cut이 정점에 생기는거니까 정점을 쪼개 줬어야 했네.

3. (i,j) 정점 쪼개서 in 정점은 i*m+j 값의 인덱스 가지게, out 정점은 i*m+j + 10000 값의 인덱스 가지게 매핑.

4. 아무리 벽 놓아도 K, H가 이어지지 않는 경우는 처음에 K,H가 인접해 있는 경우구나 !! 이거 맨 먼저 걸러줘야지



아무래도 3번에 문제가 있는 것 같은데요... 고수님들의 도움 바랍니다 ㅜㅜ 

오랫만에 유량 개념 감좀 잡을려고 했는데 어렵네유 ㅜㅜ

zlzmsrhak   4년 전

1. 제 컴퓨터에서는 예제가 0이 나오는데 잘못된건가요?

2. dual 변수가 역간선인 것 같은데 e1의 역간선이 e4인 것은 이해가 잘 되지 않습니다.

cokcjswo   4년 전

답변 감사합니다.


1. 잦은 수정으로 잘못된 버전의 소스를 올렸네요 죄송합니다 !

고친 소스를 댓글에 첨부합니다.


2.

이렇게 좌표로 주어진 정점을 네트워크 플로우에 많이 활용 해보지 않아 실수 한 것 같습니다

다음과 같이 수정해보았는데 어떤지요?

주석 참고해주시면 감사하겠습니다.



cokcjswo   4년 전

맞았습니다 !!


이것저것 구글링 하며 찾아보니


유향 간선으로 처리해야 하더군요 !! (왜인지는 잘 모르겠지만...)


정점을 컷하면 유향으로 처리해줘야하는건가? 라는 생각도 듭니다.


아니면 정점 컷 과 상관 없이 문제에서 유향간선을 요구하고 있는건가요?


하... 어렵네요...



cokcjswo   4년 전

아는 분께 물어서 해결했습니다 !!


무향간선을 어떻게 쪼갤지 얕게 알고만 있어서 문제가 생겼었네요 !!


도움주신

zlzmsrhak 

 님 감사합니다 !

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