전체 글 (704) 썸네일형 리스트형 네트워크 유량. [2316] [1. 문제 설명] https://www.acmicpc.net/problem/2316 [2. 풀이 접근] 유량 네트워크로 접근해야 한다. 단, 특정 도시(이하 정점) 을 여러번 지나갈 수 없다. 포드-풀커슨 알고리즘은 간선의 유량에 대해서 동작한다. 따라서, 정점을 간선처럼 만들어야 한다. # 이하 코드 주석 참조. 주의 할 점. 정점을 간선처럼 만들 때는, 연결 된 두 도시를 입력받는 시점에서 만들면 안된다. 모든 입력을 받고 나서, edge 를 순회하면서 확인해야 한다. => 원하는 형태 : {u1 -> u2} -> {v1 -> v2} => 잘못된 형태 : {u1 -> u2} v2} \ > {z1 -> z2} # 즉, 이미 정점 u 는 사용하였는데, 정점 v 에서 u2 와 연결되고, u2->z1 간선.. 이분매칭 [1. 개요] 이분 매칭을 설명하기에 앞서 이분 그래프에 대한 개념 정의 그래프의 모든 정점이 두 그룹으로 나누어 질 때 서로 다른 그룹의 정점들은 연결되지만 같은 그룹의 정점들은 서로 연결하지 않는 형태의 그래프 두 집합 간의 대응 관계를 표현하기 위해 사용 https://testkernelv2.tistory.com/338 매칭 그래프에서 끝점을 공유하지 않는 간선의 집합을 의미한다. 여기서 끝점을 공유하지 않는다는 의미는 아래와 같다. 두개 이상의 간선이 공유하는 정점이 있는 경우. 아래와 같은 형태의 그래프에서 어떤 조건을 만족하는 edge 만 선별하였다고 가정했을 때, 빨간색 간선이 선별된 edge 그래서 매칭 문제(최대 매칭 문제) 는 그래프에서 가장 큰 매칭을 찾는 문제를 말하며, 가장 큰 매.. 네트워크 유량. [17412] [1. 문제 설명] https://www.acmicpc.net/problem/17412 [2. 풀이 접근] 인접한 두 도시를 연결하는 edge 의 용량을 1로 하는 유량 네트워크에서 포드-풀커슨 알고리즘을 이용하여 최대 유량을 계산한 결과는 Source 에서 Sink 로 가는 겹치지 않는 경로의 개수가 된다. 자세한 설명은 코드 주석 참조. [3. 코드] 이전 1 ··· 40 41 42 43 44 45 46 ··· 235 다음
