SPFA2 [BOJ] 백준 11408번: 열혈강호 5 MCMF (minimum cost maximum flow) 알고리즘을 사용하는 문제. 할 수 있는 일을 매칭하기 위하여 NF (Network Flow) 를 수행, 이 때 최소 비용을 구하기 위하여 SPFA + SLF 수행 #include #include #include #include using namespace std; int n, m; int ca[802][802]; int fl[802][802]; int cost[802][802]; int S = 0, D = 801; vector v[802]; int main() { cin >> n >> m; for (int i = 1; i > mo; cost[i][w + 400] = mo; cost[w+400][i] = -mo; v[i].push_back(w + .. 2020. 6. 22. [BOJ] 백준 1865번: 웜홀 SPFA + SLF 로 풀었지만 일반적인 벨만포드 알고리즘이 더 빠름 웜홀 시작점을 저장하여 탐색하며 update 횟수를 cycle 배열에 저장하여 노드 수 이상 업데이트 되면 음의 사이클 [!] 노드 수가 N개일때 N개를 전부 탐색하는 path는 n-1 개이다 n번 탐색이 된 경우는 n-1번 움직였을때보다 최소의 경로 비용을 뜻하므로 음의 간선이 있음 #include #include #include #include #include #include #include using namespace std; typedef pair pii; typedef long long ll; void solve() { int n, m, w; vector v[501]; vector list; cin >> n >> m >> w;.. 2020. 6. 19. 이전 1 다음
