oVeron

격자 그래프는 이분 그래프라는 점을 이용하여, 최소 비용으로 최대 매칭을 찾으면 된다. 단 주의할 점이 2가지 있다.1. 구하고자 하는 값은 두부의 최대 가치이다. '11409번: 열혈강호 6'에서와 마찬가지로 간선의 비용의 음양을 바꿔야 한다.2. 최대 매칭을 찾는다고는 했지만, 가치가 F인 두부의 경우에는 매칭시킬 경우 전체 두부의 가치가 작아지는 때가 있다. 때문에 SPFA 알고리즘으로 찾은 증가 경로의 가중치 합이 양수인 경우 바로 알고리즘을 종료해야 한다. 간선의 비용의 음양을 바꾸었기 때문에 증가 경로의 가중치 합이 양수라는 뜻은 원래 전체 두부 가치가 떨어졌다는 뜻과 같기 때문이다.#include using namespace std;typedef long long ll;typedef pair..

알고리즘/baekjoon 2024. 7. 7. 10:34