알고리즘/메모44 고속 푸리에 변환 (FFT) blog.myungwoo.kr/54 비재귀적으로 구현하신 페이지. 많은 분들이 이 코드를 사용하시는 듯 함 합성 곱을 $O(nlogn)$ 에 구할 수 있다. 자세한 설명은 다른 블로그.. #define _USE_MATH_DEFINES #include #include #include using namespace std; #define sz(v) ((int)(v).size()) #define all(v) (v).begin(),(v).end() typedef complex base; void fft(vector & a, bool invert) { int n = sz(a); for (int i = 1, j = 0; i > 1; for (; j >= bit; bit >.. 2021. 1. 2. 최대 유량 - 디닉 jason9319.tistory.com/150 blog.naver.com/kks227/220808685331 위 두 블로그에서 공부했습니다. 특히 코드는 jason님의 코드를 많이 참고했습니다. $O(V^2E)$ 1. bfs로 각 정점마다 소스로부터 얼마나 떨어져있는지 의미하는 level 배열을 초기화 해준다. 싱크에 도달할 수 있다면 2. 소스-싱크 경로상 차단 유량을 구해준다. dfs에 지금까지 최소 유량을 같이 보내주고 반환값을 이후 최소 유량으로 설정하면 쉽게 구할 수 있다. 차단 유량이 0보다 크다면 반복한다. dfs할 때 역방향 간선 때문에 한 정점을 여러번 접근할 수 있다. work배열로 정점 u를 여러 번 접근하더라도 dfs 진행에 있어서 다음 정점 v를 중복해서 접근하지 않도록 한다. w.. 2020. 10. 9. 이분매칭 blog.naver.com/kks227/220804885235 라이님 블로그에서 공부했음을 밝힙니다. 설명은 라이님 블로그 정독 이분그래프에서 최대 매칭 수를 반환한다. 하나의 class의 모든 정점을 돌면서 각 정점마다 최악의 경우 모든 간선을 확인하게 된다. $O(VE)$ Hopcroft-Karp Algorithm($O(E\sqrt{V})$)로 대체 가능하다. www.acmicpc.net/problem/17412 각 소마다 원하는 축사가 있다. 가장 많은 소를 축사에 배정하라. 이분매칭 const int MAX = 201; //A[i] : A그룹의 i번째와 매칭된 B그룹의 정점번호 int n, m, A[MAX], B[MAX]; vector g[MAX]; bool vst[MAX]; //A그룹의 정점 u.. 2020. 10. 7. 최대 유량 - 에드몬드 카프 blog.naver.com/kks227/220804885235 라이님 블로그에서 공부했음을 밝힙니다. 설명은 라이님 블로그 정독. $O(min(VE^2, Ef))$ 단방향 그래프인 경우 1. capacity를 적절한 간선에만 뚫어줘야 한다. 2. 역방향 간선도 인접리스트에 같이 추가해줘야 한다. (capacity로 구분되는 것) 양방향인 경우, u-v, v-u간선에 모두 capacity를 뚫어줘야 함. www.acmicpc.net/problem/17412 각 소마다 원하는 축사가 있다. 가장 많은 소를 축사에 배정하라. 소를 향하는 더미 노드와 간선, 축사에서 향하는 더미노드와 간선을 추가해서 capacity가 1인 최대유량을 흘려주면 된다. 단방향 그래프임에 주의. 소 n마리 축사 m개인데, 축사의 정.. 2020. 10. 7. 이전 1 2 3 4 ··· 11 다음
