oVeron

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

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

1.동전의 위치를 맞바꾼다는 것은 곧 두 정점을 잇는 간선을 이용한다는 뜻이다. 동전을 교환하는 횟수를 간선의 가중치라 생각하면, 각 정점을 이은 간선의 가중치를 전부 1이라 설정할 수 있다. 결국 이 문제는 간선의 가중치가 전부 1인 그래프에서, 정해진 정점들(검정 동전, 검정색 정점)을 최대 매칭시키는 최소 가중치의 합을 구하는 문제이므로 이 문제는 MCMF로 해결할 수 있다. 2.\(source\)와 \(sink\)를 연결하는 간선의 비용은 0, 나머지 간선의 비용은 1이다.\(source\)와 \(sink\)를 연결하는 간선의 용량은 1이며, 나머지 간선의 용량은 제한이 없으므로 \(INF\)로 설정한다.간선이 양방향이기에 비용 음양 설정에 주의한다. 정방향으로 유량이 흐를 때, 역방향으로 유량을..

알고리즘/baekjoon 2024. 7. 7. 09:20

MCMF 기본 문제#include using namespace std;typedef long long ll;typedef pair pii;typedef pair pll;typedef tuple tiii;const int INF = 1e9;const int MAXN = 401;int N, M;int S, T;int cap[MAXN*2][MAXN*2], fl[MAXN*2][MAXN*2];vector graph[MAXN*2];int par[MAXN*2], dist[MAXN*2];bool inQ[MAXN*2];bool SPFA(){ memset(par, -1, sizeof(par)); fill(dist, dist + MAXN*2 + 1, INF); memset(inQ, false, sizeof(..

알고리즘/baekjoon 2024. 7. 6. 10:35