알고리즘76 [알고리즘 정리]네트워크 플로우(Network Flow) 알고리즘_에드몬드 카프 알고리즘(Edmonds-Karp algorithm) 네트워크 플로우 코드적으로 이해하는것이 조금 어려울 수 있지만, 개념자체는 간단하게 "도착지(Sink)에 얼마나 물이 나오게 할 수 있느냐?"에 관한 문제입니다. 그림을 보면 쉽게 이해 할 수 있다. 위의 문제에서 각 Source와 각 수도관은 주어진 리터만큼 시간당 물을 보낼 수 있고 하였을때, Sink에는 시간당 얼만큼의 물이 도달 할 수있냐? 딱, 봐도 8L의 물이 도달 할 수 있다는 것을 알 수 있다. 이 문제를 해결 하는 것이 네트워크 플로우다. 용어 정리 & 주요 특징 - (용어 1) Source : 네트위크(물)의 시작점 - (용어 2) Sink: 네트워크(물)의 도착지점 - (용어 3) c(a,b) : a->b로 흐를 수 있는 물의 최대량(용량) - (용어 4) f(a,b) : a->b로 .. 2018. 10. 3. [알고리즘 정리] 위상 정렬 위상 정렬 시간 복잡도 : O(|V|+|E|) indegree : 한 정점에 들어오는 간선 수ex ) a -> c, b -> c 라면 c의 indegree는 2, a,b의 indegree는 0이 된다. 기본 코드 // 해당 노드에 향하는 간선(indegree)이 0인경우 q에 추가한다. for (int i = 1; i 2018. 9. 30. 백준(BOJ) 1298 노트북 주인을 찾아서 ** # 이분매칭 # 네트워크 플로우 네트워크 플로우를 이용하여 풀수도 있지만,네트워크 플로우 보다는 이분매칭을 이용하면 보다 쉽게 풀 수 있다. #include #include #include #include #include #include #include #include #include #define MAX 5005 #define INF 987654321 #define MOD 31991 #pragma warning(disable:4996) using namespace std; typedef long long ll; typedef pair pi; int n, m, bs[MAX]; bool visite[MAX]; vector node; bool dfs(int cur) { if (visite[cur]) retu.. 2018. 9. 30. [알고리즘 정리] 이분 매칭 이분 매칭 시간 복잡도 : O(E*sqrt(V)) visit : 방문 여부 확인bs : 현재 노드가 연결된 노드 ex) bs[a]=b; 라면, a와 b가 연결된 상태이다. 기본 코드 bool dfs(int cur) { if (visite[cur]) return 0; visite[cur] = 1; for (int i = 0; i < node[cur].size(); i++) { int next = node[cur][i]; if (!bs[next] || dfs(bs[next])) { bs[next] = cur; return 1; } } return 0; } int binary_match() { int ret = 0; for (int i = 1; i 2018. 9. 30. 이전 1 2 3 4 5 ··· 19 다음
