lyzqm   4년 전

이 문제 힌트보고 풀긴 풀었는데 기차에서 내리는작업을 i번째와 i+1번째 정점을 capacity가 INF, cost 0으로 연결해주는 작업으로 

해주는데 직관적으로 이해하기가 어렵네요 ㅠㅠ

설명해주실분 있나요?

smu201111192   4년 전

코드를 보여주실 수 있나용?

lyzqm   4년 전

여기있습니다 !

smu201111192   4년 전

n->n+1을 연결해주는게 사람을 내려주는게 아니지 않을까요?

초기상태에는 total (버스의 총 용량)만큼 flow를 쭉 흘릴 수 있는 파이프가 준비되어있습니다 (mcmf.add_edge(n,n+1,INF,0) 만을 이용해 1->n으로 flow를 흘리면 버스의 용량만큼 보낼 수 있습니다.) 물론 이경우 손님을 태우지 않으니 얻는 이익이 없습니다.

여기서 n->m으로 가는 손님 k명을 태운다면

mcmf.add_edge(n,m,a[n][m],-c) 이 엣지를 이용해서 n->m으로 k만큼 흘리게되죠.

n->m으로 파이프(mcmf.add_edge(n,n+1,INF,0) 로 total만큼 흘릴 수 있는 상태였는데

mcmf.add_edge(n,m,a[n][m],-c) 요녀석으로 k를 흘렸으니

파이프로 흘릴 수 있는 flow는 total-k가됩니다.

매순간 파이프(mcmf.add_edge(n,n+1,INF,0)로  흘릴 수 있는 플로우의 양을 버스에 사람을 얼마나 더 태울 수 있는지로 생각하면 좋을거같네요.

mcmf.add_edge(n,m,a[n][m],-c) 로 흘린 flow는 k (n->m으로 가는 손님 k명을 태움) 

mcmf.add_edge(n,n+1,INF,0) 로 n->m으로 흘릴 수 있는  flow는 total-k (버스에 사람을 total-k 명 더 태 울 수 있음)

m+1이후로는  mcmf.add_edge(n,m,a[n][m],-c) 로 흘린 flow k가 다시 돌아와서

mcmf.add_edge(n,n+1,INF,0)로 흘릴 수 있는 엣지가 다시 total 이됩니다.  (n->m으로 가는 손님 k명이 m에서 내렸으니 m+1부터는 버스에 태울 수 있는 사람수가 다시 total이됨)

smu201111192   4년 전

mcmf.add_edge(n,n+1,INF,0)로 흘릴 수 있는 플로우 가 다시 total 이됩니다 

lyzqm   4년 전

으어 가치관에 혼란이오네요 ㅠㅠ

제가 n->n+1을 연결해주는게 내린다고 생각한 이유가 "내리는 작업을 시행하지 않았을 때" 다음 그림처럼 모델링을 했었는데요.

(즉, 사람들이 타기만 했을때)

p.png앞서말한 n->n+1을 연결했을 때의 경우가 제외되어있는 상태입니다. (물론 간선마다 capacity와 cost가 적용되있음)

그렇다면 이 모델링또한 잘못된건가요?

smu201111192   4년 전

위에 그려주신 그림에서 1->2 ,2->3 3->4 연결되는 inf 간선(빨강 간선)을 만들어 주셔야됩니다.

smu201111192   4년 전

KakaoTalk_Photo_2017-09-10-00-48-40.jpeg


실수로 1->2 ,2->3 로 가는 초록색 간선을 2개나 그렸네요, x표시 친거는 없다고 생각해주세요.

버스의 총용량: total

빨강 간선만을 이용해서 source->sink로 flow를 흘리면  total만큼 흘릴 수 있습니다.(사람을 안 태움)

여기서 초록색 간선을 이용해서 1->2로 k만큼 흘린다고 생각해볼게요.

빨강간선을 이용해서 1->2로 total 만큼 흘릴 수 있었는데 (사람을 total만큼 태울 수 있었는데)

k만큼 초록색간선으로 흘렸으니 빨강 간선으로 (1->2)로 total-k만큼 흘릴 수 있습니다. (1->2로 가는 사람 k명을 태웠으니

1->2 구간에서는 total-k만큼 사람을 더 태울 수 있습니다.)

2->3부터는 1->2로 연결된 초록색 간선의 flow k를 돌려받아서 다시 

total 만큼 보낼 수 있는 상황이됩니다.

빨강 간선으로  흘릴 수 있는 flow를 버스의 남은 좌석이라고 생각하시고,

n->m으로 가는 초록색간선으로 flow를 흘리는것을 n->m으로 가는 사람을 태운다고 생각하시면 좋을거같아요.

m에서  다시 해당 flow를 돌려받고 (손님이 내리고)


smu201111192   4년 전

노랑책이 있으시다면 p311 문제를 보시면 좋을거같습니다. 

거의 똑같은 문제가 있어요.~

smu201111192   4년 전

(i->i+1) 빨강 간선의 역할은 사람을 내리는 간선이 아니고, 

버스에 현재 태울 수 있는 사람을 나타내는 간선입니다.


lyzqm   4년 전

와 코드에 대입해서 시뮬레이션 돌려보니 이해가 됬네요.

결국은 내리는 작업이 어떠한 방식으로 구분되는것이 아니라 간선에서 flow를 다시 돌려받는 형식으로 계산하는거군요..

모델링할때 이정도까지 생각하기도 힘든것 같네요 


저번에도 도움주셨던것 같은데  친절한 설명 감사합니다 ㅠㅠ 복받으시길

smu201111192   4년 전

와~ 축하드립니다.

https://www.acmicpc.net/proble... 

요문제도 풀어보시면 좋을거같네요 .

모델링은 비슷한데 아이디어가 하나 더 필요한 문제에용

lyzqm   4년 전

캬 추천문제까지 !

감사합니다. 꼭 풀어보겠습니다!


jwvg0425   4년 전

역시 네트워크 플로우 장인 스무님.. 

smu201111192   4년 전

헐 갓이 칭찬해주시다니 영광입니다~


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