https://www.acmicpc.net/problem/4013 주어진 그래프에서 목표 지점 중 하나까지 도달하는 경로 중 최대 cost를 얻을 수 있는 값을 구하는 문제입니다. 먼저 각 경로를 SCC로 묶으면, SCC 내에서는 해당 노드 cost 합을 얻을 수 있습니다. 그리고 SCC 간의 그래프에 대해 경로 찾기 알고리즘 등으로 최대 cost를 계산하면 됩니다. 그리고 계산된 각 scc까지의 최대 cost에 대해, 커리 가게 존재 유무를 체크하여, 최종 결과를 구하면 됩니다. 저는 edge 개수와 node 개수 최대값이 동일해, SPFA를 적용했습니다.(다익스트라도 해보니 통과하긴하지만, 아무래도 sparse한 그래프라 더 느림) 코드는 아래와 같습니다. #include #include #incl..
https://www.acmicpc.net/problem/2389 최대 100개의 점을 모두 포함하는 원의 중심과 반지름을 구하는 문제입니다. 2차원에서 원은 3개의 점으로 구할 수 있습니다. 2개의 점을 지나는 최소 원은 선분을 지름으로 하는 원입니다. (이와 같은 논리로 d차원에서는 affine independent한 d+1개의 점이 있으면, 그 점을 지나는 boundary는 유일하게 결정됩니다.)(참고 : https://freshrimpsushi.github.io/ko/posts/2385/) 100개의 점을 대상으로 100C1, 100C2, 100C3 케이스에 대해 원을 구성하고, 100개의 점들과 포함유무를 확인하는 브루트포스 방식도 가능합니다. (대충 복잡도 계산해보면 1600만 정도 돌아야 함..
https://www.acmicpc.net/problem/17412 도시 정보가 주어져 있을 때, 1번이 source, 2번이 sink인 그래프에서 최대 유량을 구하는 문제와 동일합니다. 1번에서 2번으로 가는 최대 경로 개수는 결국 모든 엣지의 cap이 1인 상황에서 최대 유량을 구하는 것과 동일합니다. 최대 유량을 구하는 기법 중 빠른 것으로 알려진 Dinic 알고리즘을 적용해보았습니다. Dinic 알고리즘에 대한 설명 및 구현은 아래 글들을 참고하였습니다. https://gazelle-and-cs.tistory.com/84 디니츠의 알고리즘 (Dinitz' Algorithm)지금까지 저는 제 블로그에서 최대 흐름 문제(maximum flow problem)를 많은 포스트를 통해서 다루어 왔습니다...
최대 유량 문제 : 그래프에서 가능한 최대 유량을 구하는 문제이분 매칭 문제 : bipartite graph에서 매칭 개수를 최대로 정하는 문제 MCMF : 각 엣지 별 비용이 있을 때, 최대 유량을 만족하는 최소 비용을 구하는 문제 할당 문제 : bipartite graph에서 매칭하고, 각 엣지 별 비용이 있을 때, 최대 매칭 시 최소 비용을 구하는 문제 (주로 1대1 대응 관계로 perfect matching 시 최소 비용을 계산) 즉, 이분 매칭은 최대 유량에서 모든 엣지의 cap이 1인 case, 할당 문제는 MCMF에서 모든 cap이 1인 case를 의미한다. (단 bipartite graph는 만족해야 함) 최대 유량 문제 계산 기법 1. Ford-Fulkerson : 최대 유량을 계산하..
이분매칭(bipartite matching)은 정점들의 집합 간의 매칭을 계산하는 문제입니다. bipartite graph와 bipartite matching에 대한 설명은 아래 글을 참고하면 좋습니다.https://gazelle-and-cs.tistory.com/12 쾨니그의 정리 (Kőnig's Theorem)이 글은 홀의 정리 (Hall's Theorem)와 밀접한 연관이 있습니다. 필요한 경우에는 이를 참조하세요.2019/01/28 - [조합론적 최적화] - 홀의 정리 (Hall's Theorem) 무언가를 최적화시키는 문제를 보면 생각보gazelle-and-cs.tistory.com https://gazelle-and-cs.tistory.com/35 호프크로프트-카프 알고리즘 (Hopcroft-..