알고리즘225 이분매칭 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. 난수, 랜덤 #include using namespace std; int main(){ random_device rd; //진짜 난수 발생 mt19937 mt(rd()); uniform_int_distribution rnd(0, n-1); //min-max 폐구간 범위 //rnd(mt) -> 0~n-1사이 난수 생성 } random_device 객체 rd는 rd()로 unsigned int범위(0~4294967295) 난수를 생성한다. mt19337은 균등한 분포의 난수를 만들어주는 난수 엔진이다. 이 객체를 만들 때 생성자에 random_divce 객체를 넣어서 만들면 된다. uniform_int_distribution도 유사한 난수 엔진인 것으로 보인다. 2020. 8. 28. BOJ 11003 - 최솟값 찾기 (monotonic queue) https://www.acmicpc.net/problem/11003 풀이참고 https://jason9319.tistory.com/346 길이 n의 배열이 주어질 때, 구간 크기가 L인 모든 구간에서 순서대로 구간 최소값을 구하라 ( $n> n >> l; for (int i = 0; i a[i]; while (!dq.empty() && dq.back().first >= a[i]) dq.pop_back(); dq.push_back({ a[i], i + l }); cout 2020. 8. 12. 이전 1 2 3 4 5 ··· 57 다음