kkw564   2년 전

도시를 왕복해야하는데 왜 저는 왕복을 못하는걸까요?

문제에서 source와 sink를 뺀 한번 방문한 노드는 다시 방문 할 수 없다고 하여, visit배열을 써서 구현했습니다.


하지만 저는 76퍼센트와 92퍼센트짜리 도시를 왕복못하고있습니다.


어떤 면에서 잘못됐는지 도와주시면 정말 감사히 도시 왕복을하겠습니다.

lyzqm   2년 전

모델링이 잘못된거같습니다.

이 문제는 1,2번 정점을 제외한 나머지 정점은 단한번만 방문해야하는게 핵심인데 

"정점분할"이라는 방식을 사용하면 해결할 수 있습니다.


예를 들어 3번정점을 3(in), 3(out)으로 두개의 정점으로 분할해서 이 사이의 용량을 1로 제한하면 유량이 한번흐르고 더이상 흐르지 못하므로

단 한번만 방문하는것을 구현할 수 있습니다.



ehddml3   2년 전

6 7

1 3
3 4
4 2
1 6
6 4
3 5
5 2

이런 식으로 강제적으로 첫 증가경로를 가로지르게 만들면 해당 그래프에서는 2가 나와야할 것 같은데 1이 나옵니다.

http://kks227.blog.me/22080488... 에 도시왕복 풀이에서 개념에 대한 그림이 있습니다. 노드 한 개를 내부 노드 두 개로 나누어서 그 두 노드 사이의 용량을 1로 두고 network flow를 돌리는 것인데 한번 읽어보시길..

kkw564   2년 전

@lyzqm

모델링 하는법을 한번 봤는데, 그런데 하나의 노드를 두개로 쪼개어 유량을 계산하는것과, 그냥 하나의 노드가 방문되었다면 true를 하는것과의 차이가 날수있나요?

smu201111192   2년 전

역변을 통해 유량을 되돌려야 될때 문제가 될 수 잇지않을까요 visit로 막아서 못 흘릴거 같아요

kkw564   2년 전

다들 감사합니다

플로우를 새로 공부해야겠다고 느꼈습니다.

제대로 알고있지 못했네요

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