15개의 댓글이 있습니다.
-
-
chochogogo -
답변 감사합니다~!
여쭙고 싶은 것이 있는데요...
답변 주신 링크에 flow 처리 시, flow 역 방향으로 cost를 음수 처리해주는 것도 처리해 줄 필요 없는 것인가요??
(처리를 안해 주어도 flow 흐름에 따라 자동 음수 계산 되는 것인가요???)
우문이라면 죄송합니다 ㅠㅠ
8년 전 link
-
-
-
chochogogo -
아하! 그렇군요!!!!!!!!!!!!!!!
답변 감사합니다!!!
아참 마지막으로 또 질문 드려도 될까요?ㅠㅠㅠ
기본 network flow가 확대 경로가 없을 때까지 process를 진행한 후,
t에 도달하는 flow의 합이 최대 유량이 되는데,
MCMF의 경우, 동일하게 확대 경로가 없을 때까지 process를 진행(단, cost 기준으로), 확대 경로를 찾을 때마다다(t에 도착할 때마다) flow를 갱신해 주기 위해 t로부터 역탐색을 하게 되는데, 이때 임의의 변수x에 해당 경로의 cost들의 총 합을 계속 더해줌.
확대 경로가 없을 때까지 process 진행 후 x의 값이 minimum cost이다.
가 맞는 것인가요??
자꾸 질문드려 죄송합니다 ㅠㅠ
8년 전 link
-
-
-
chochogogo -
두분 다 친절한 답변 정말 감사합니다~!!!!!!!!!!!!!!
8년 전 link
-
-
-
chochogogo -
JongMan님께서 올려주신 링크 보았는데요~~
질문이 드리고 싶은게 생겨서요..ㅠㅠ,
Ver1. 에서
if(flow[v][u] > 0)
cand = distance[u] - cost[v][u];
else if(cap[u][v] > flow[u][v])
cand = distance[u] + cost[u][v];
를
if(cap[u][v] > flow[u][v])
if(flow[u][v] < 0)
cand = distance[u] - cost[v][u];
else
cand = distance[u] + cost[u][v];
로 생각해도 될까요???ㅠㅠ
8년 전 link
-
-
-
chochogogo -
매번 질문 드릴때 마다 답변 주셔서 감사합니다~!
주말 잘 보내세요~~
8년 전 link
-
-
-
chochogogo -
종만님께서 코드 공유해 주신것 공부한 덕분에 문제를 풀 수 있었습니다!
(위의 문제 아닌 다른 문제)
근런데 ver1로 문제를 풀었는데 답은 모두 정상적으로 나오는데 시간 초과가 되더라구요. 그래서 ver2(우선순위 큐 이용)을 공부하여 코드 구현중에 질문하고 싶은것이 있어 글 남기게 되었습니다.여쭙고 싶은 내용 :
1. 제가 C로 구현하고 있는데, 우선순위 큐를 구현하기 위해 배열을 잡아 힙을 구현하였는데, 크기를 얼마나 잡아야 하는지 여쭙니다... 원래 다익스트라의 경우, 출발지가 됬던 정점은 checked(visited) 처리가 되어 pq에 인큐 안하는데 해당 case에서는 pq 배열의 크기를 얼마나 잡아야 하는 건지 여쭙니다 ㅠㅠ
2.
int cost = -pq.top().first;
pq.push(make_pair(-thereCost, there)); 에서 -pq.top().first와thereCost앞에 -붙는 이유위의 두가지 여쭙니다.
감사합니다.
수고하십시오~!
8년 전 link
-
-
-
chochogogo -
2번 질문 같은 경우는
알고리즘 문제 해결전략에서, priority_queue는 기본적으로 가장 큰 원소가 위로 가도록 큐를 구성하기 때문에 거리의 부호를 바꿔서 거리가 작은 정점부터 꺼내지도록 하는 것에 주목합시다.
라고 적어주신 것처럼, STL이 가장 큰 원소가 위로 가도록 구현 되어 있기 대문에 그런것 인가요??
8년 전 link
-
-
-
chochogogo -
답변 감사합니다!
8년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
chochogogo
안녕하세요?
네트워크 플로우 관련 이론 중
-기본 최대 유량 이론
-이분 매칭
-minimum cost maximum flow
에 대해 공부하고 있는데요...
-기본 최대 유량 이론
-이분 매칭
는 이해가 가는데....
-minimum cost maximum flow는 어떻게 구현해야 할지 감이 안잡혀서요....
(http://jungol.co.kr/problem.php?ctc=031200&id=1882 문제가 MCMF 문제 인것 같은데..ㅠㅠ)
일단 해당 건 관련해서 알고 있는 것은....
minimum cost maximum flow 구현 시 기존
여기서 궁금한 점이... 밸만포드로 확대경로 구한 후에 flow는 기존 알고리즘 대로 최저 flow 만큼씩 빼주면 되는 걸로 알고 있는데
cost에 대한 처리는 어떻게 되어야 하는건가요...??
그리고 솔직히 말씀 드리면, minimum cost maximum flow도 그냥 넘어 알고 있는 내용이라 제가 쓴 내용이 맞는지도 모르겠습니다...ㅠㅠ
8년 전