huhsae's day huhsae's day

2188 축사 2188 축사https://www.acmicpc.net/problem/2188 분류네트워크 유량애드몬드-카프 알고리즘BFS이분 매칭 TIPS포드 - 풀거슨 알고리즘을 풀 때, v -> u로 가는 용량이 주어진다면, u -> v로 가는 용량 0의 간선을 만들어 주어야 한다.코드에서는 capacity[][] 배열을 사용해서 그래프를 나타내준다면, 초기값이 0이기 때문에 1번의 내용을 생각해줄 필요가 없다. 하지만 간선 찾는 시간을 단축시키기 위해 인접리스트로 그래프를 표현했다면, 꼭 인접리스트에 반대로 가는 가상의 간선을 만들어주어야한다. 처음부터 그래프를 배열로 했다면 상관없다.이분 매칭은 source와 sink가 여러개인 네트워크 유량문제에서 super source와 super sink를 ..