알고리즘/메모44 최소 스패닝 트리 크루스칼 O(ElogE) 필요한 것: union-find (merge 병합성공여부 반환) 간선구조체 - 가중치 기준으로 오름차순 정렬하기 위함. int uf[100001]; int find(int a) { if (uf[a] < 0) return a; return uf[a] = find(uf[a]); } bool merge(int a, int b) { a = find(a); b = find(b); if (a == b) return false; uf[a] = b; return true; } struct Edge { int u, v, w; Edge(int u1, int v1, int w1) : u(u1), v(v1), w(w1) {} bool operator < (const Edge& O) const { re.. 2019. 8. 18. 플로이드 와샬 모든 정점간 최단거리를 구해내는 알고리즘 O(V^3) 벨만 포드로 모든 정점간 최단거리를 구하려면 O(V^2 * E) 이므로 벨만포드보다 빠르다. 필요한 것: dist[MAX][MAX] = {입력값 | 연결안됐으면INF} for(int k=0; k 2019. 8. 18. 벨만포드, SPFA 시작점을 정해줬을 때, 최단경로 알고리즘. 가중치가 음수여도 가능하다 *모든 간선을 돌면서 그에 속하는 정점에 대한 dist를 초기화할 수 있다면 초기화 해주는 작업을 정점개수-1만큼 반복한다. O(EV) 필요한 것: int dist[MAX]{0} vector adj[MAX]; //혹은 vector edge 일반적인 코드. 음의 사이클 검출방법 int main() { int N, M, dist[MAX], st, en; fill(dist, dist + N, INF); vector adj[MAX]; dist[st] = 0; bool minusCycle = false; for (int k = 0; k < N; k++) { // (N-1)번의 루프, N번째루프에 갱신되면 음의사이클존재 //이하 두개의 for문 .. 2019. 8. 18. 다익스트라 시작점이 정해진 상태이고 가중치>=0일 때 최단경로 구할 때 사용. 사이클이 있어도 사용가능. 하나의 정점을 검사할 때마다 모든 간선에 대해 검사하고, 최소힙(우선순위 큐)에 들어가는 것은 최악의 경우 간선 개수만큼 들어가므로 O(ElogE) bst(set)을 사용해서 유효한 {dist, i}만을 유지한다면 O(ElogV)지만 속도가 크게 차이 안날 뿐더러, 우선순위 큐의 시간복잡도 상수가 더 작다. 구현이 편한 ElogE코드를 사용하자 필요한 것 : bool vst[MAX] {0} int d[MAX] {INF} vector g[MAX] priority queue (dist 가장 가까운 것부터) int main() { bool vst[MAX] = {0}; vector g[MAX]; //{도착지,가중치} .. 2019. 8. 18. 이전 1 ··· 7 8 9 10 11 다음