최대 유량 관련 10 문제 (Maximum Flow) + 플로우 네트워크 20 문제

최대 유량 관련 문제 (Maximum Flow)

 

Problem 1: Dinic's Algorithm Implementation
설명: 주어진 플로우 네트워크에서 최대 유량을 찾는 문제입니다.
핵심 개념: Ford-Fulkerson, BFS, DFS, Dinic's Algorithm.

Problem 2: Bipartite Graph Maximum Matching (GeeksForGeeks)
설명: 이분 그래프에서 최대 매칭을 찾는 문제입니다.
핵심 개념: 최대 유량, 이분 그래프 매칭.

Problem 3: Max Flow in Network (SPOJ - FASTFLOW)
설명: 네트워크에서 최대 유량을 찾는 문제입니다.
핵심 개념: Ford-Fulkerson, Push-Relabel Algorithm.

Problem 4: Minimum Cut of Graph (SPOJ - UCV2013)
설명: 플로우 네트워크에서 최소 컷을 찾습니다.
핵심 개념: 최대 유량 - 최소 컷 정리.

Problem 5: Edmonds-Karp Algorithm Application (GeeksForGeeks)
설명: BFS를 사용하여 플로우 네트워크의 최대 유량을 계산합니다.
핵심 개념: Edmonds-Karp Algorithm, BFS, 플로우 네트워크.

Problem 6: Circulation in Network (Codeforces)
설명: 네트워크의 유량 순환을 계산하는 문제입니다.
핵심 개념: 네트워크 순환, 최대 유량.

Problem 7: Water Distribution (GeeksForGeeks)
설명: 마을에서 물을 분배하기 위해 필요한 최소 파이프를 찾습니다.
핵심 개념: 플로우 네트워크, 크루스칼 알고리즘.

Problem 8: Maximum Number of Accepted Invitations (LeetCode 1820)
설명: 사람과 테이블 간의 매칭을 최적화하는 문제입니다.
핵심 개념: 이분 그래프 매칭, 최대 유량.

Problem 9: Project Assignment Problem (GeeksForGeeks)
설명: 프로젝트와 작업자를 최적으로 배정하는 문제입니다.
핵심 개념: 최대 유량, 매칭 문제.

Problem 10: Maximal Matching in a Graph (Codeforces)
설명: 그래프에서 최대 매칭을 찾는 문제입니다.
핵심 개념: 매칭 문제, 플로우 네트워크.

 

플로우 네트워크 문제 목록

Problem 1: Find the Maximum Flow (GeeksForGeeks)
설명: 주어진 플로우 네트워크에서 최대 유량을 찾습니다.
핵심 개념: Ford-Fulkerson Algorithm, 플로우 네트워크.

Problem 2: Edmonds-Karp Algorithm (GeeksForGeeks)
설명: BFS를 기반으로 최대 유량을 계산하는 Edmonds-Karp 알고리즘을 연습합니다.
핵심 개념: BFS, 플로우 네트워크.

Problem 3: Maximum Bipartite Matching (GeeksForGeeks)
설명: 이분 그래프에서 최대 매칭을 찾는 문제입니다.
핵심 개념: 플로우 네트워크, 이분 그래프 매칭.

Problem 4: Water Distribution in a Village (GeeksForGeeks)
설명: 마을의 물 분배 문제를 최소 비용으로 해결합니다.
핵심 개념: 최소 스패닝 트리, 플로우 네트워크.

Problem 5: Circulation in a Network (Codeforces)
설명: 네트워크에서 유량 순환을 최적화하는 문제입니다.
핵심 개념: 플로우 네트워크, 순환 문제.

Problem 6: Project Assignment Problem (GeeksForGeeks)
설명: 프로젝트와 작업자를 매칭하여 최적화된 배정을 수행합니다.
핵심 개념: 최대 유량, 매칭 문제.

Problem 7: Maximal Matching in a Graph (Codeforces)
설명: 그래프에서 최대 매칭을 찾습니다.
핵심 개념: 플로우 네트워크, 매칭.

Problem 8: Maximum Number of Accepted Invitations (LeetCode 1820)
설명: 사람과 테이블 간의 매칭을 최적화하는 문제입니다.
핵심 개념: 이분 그래프 매칭, 플로우 네트워크.

Problem 9: Maximal Network Flow (SPOJ)
설명: 플로우 네트워크에서 최대 유량을 계산합니다.
핵심 개념: Ford-Fulkerson, Push-Relabel Algorithm.

Problem 10: Minimum Cut Problem (GeeksForGeeks)
설명: 플로우 네트워크에서 최소 컷을 계산합니다.
핵심 개념: 최대 유량 - 최소 컷 정리.

Problem 11: Job Assignment Problem (GeeksForGeeks)
설명: 작업자와 작업을 매칭하는 최적화 문제입니다.
핵심 개념: 매칭 문제, 플로우 네트워크.

Problem 12: Dinic's Algorithm Practice (GeeksForGeeks)
설명: 레벨 그래프를 사용하여 최대 유량을 계산합니다.
핵심 개념: Dinic's Algorithm, 플로우 네트워크.

Problem 13: Assign Tasks to Workers (LeetCode)
설명: 작업과 작업자를 매칭하여 최소 비용으로 할당합니다.
핵심 개념: 이분 그래프 매칭, 최대 유량.

Problem 14: Bipartite Graph Maximum Matching (GeeksForGeeks)
설명: 이분 그래프에서 최대 매칭을 찾습니다.
핵심 개념: 매칭, 플로우 네트워크.

Problem 15: Weighted Job Scheduling with Deadlines (GeeksForGeeks)
설명: 작업을 최적화된 방식으로 스케줄링합니다.
핵심 개념: 최대 유량, 매칭.

Problem 16: Max Flow Min Cut (Codeforces)
설명: 플로우 네트워크에서 최대 유량과 최소 컷을 찾습니다.
핵심 개념: 플로우 네트워크, 최대 유량 - 최소 컷 정리.

Problem 17: Hiring Workers to Minimize Cost (GeeksForGeeks)
설명: 작업자 고용 비용을 최적화하는 문제입니다.
핵심 개념: 플로우 네트워크, 최적화.

Problem 18: Maximum Independent Set in Graph (Codeforces)
설명: 그래프에서 최대 독립 집합을 찾습니다.
핵심 개념: 매칭, 플로우 네트워크.

Problem 19: Room Allocation Problem (Codeforces)
설명: 방을 효율적으로 할당하는 문제입니다.
핵심 개념: 최대 유량, 매칭.

Problem 20: Optimal Resource Allocation (Codeforces)
설명: 자원을 최적화하여 배분합니다.
핵심 개념: 플로우 네트워크, 매칭.