목록maximum flow (3)

답은 알고리즘 뿐이야!

[BOJ 5651] 완전 중요한 간선

문제 출처 : https://www.acmicpc.net/problem/5651 5651번: 완전 중요한 간선 입력은 여러개의 테스트케이스로 이뤄진다. 첫째 줄에는 테스트케이스의 수 K (1
알고리즘/백준문제풀이 2020. 9. 3. 20:14
[BOJ 1031] 스타 대결

문제 출처 : https://www.acmicpc.net/problem/1031 풀이 : Maximum Flow 문제입니다. 아래의 조건에 따라 푸시면 됩니다. 1. A팀의 경기수 총합 != B팀의 경기수 총합 => -1 2. A팀의 경기수 총합 != Maximum Flow => -1 3. A팀의 경기수 총합 == Maximum Flow => 사전순 정렬 이문제의 핵심은 3번 사전순 정렬인데 사전순 정렬은 엣지 하나를 고르고 엣지와 동일한 시작점에서 동일한 끝점으로 갈수있는 다른 플로우가 있는지 찾은 후 있으면 엣지의 플로우를 지워주고 경로에 Flow를 흘려주시면 됩니다. 단 찾을때 정렬을 해야하기 때문에 시작점과 끝점의 범위에 주의해야합니다. 만약 인풋이 2 2 1 1 1 1 일때, 1->3, 2->4..
알고리즘/백준문제풀이 2020. 3. 20. 18:45
[BOJ 2367] 파티

문제 출처 : https://www.acmicpc.net/problem/2367 풀이 : 네트워크 플로우 (Maximum Flow) 문제입니다. 파티에 N명의 사람이 오고 D개의 음식을 준비해야하는데 한 사람당 음식을 K개 준비할 수 있고 같은 음식은 1개만 준비할 수 있습니다. 따라서 다음과 같이 모델링 할 수 있습니다. 1. Source에서 사람으로 K만큼의 Capacity를 가진 Edge를 연결 2. 사람에서 각 사람당 준비할 수 있는 음식으로 1만큼의 Capacity를 가진 Edge를 연결 (한개의 음식은 한사람당 하나만 들고갈수 있으므로) 3. 각 음식에서 Sink로 가져올 수 있는 갯수만큼의 Capacity를 가진 Edge를 연결 예제의 경우를 네트워크 플로우로 모델링 하면 아래와 같은 모형이..
알고리즘/백준문제풀이 2020. 3. 8. 17:11
Prev 1 Next