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

열의 합을 그룹 \(A\)에 속하는 정점으로, 행의 합을 그룹 \(B\)에 속하는 정점으로 생각해 보자. \(N\)번째 열의 정점과 \(M\)번째 행을 잇는 간선의 가중치는 격자 \((N, M)\)에 들어갈 수 있는 값이 될 것이다.  이때 전체  격자에 들어갈 수 있는 값의 최댓값을 용량으로, 실제 격자에 들어갈 수 있는 값을 유량이라 생각하면, 간선의 용량을 1부터 10000까지 설정해 가면서 유량을 흘릴 수 있다. 최대 유량이 열의 합 또는 행의 합과 같으면 설정한 간선의 용량으로 숫자판을 만들 수 있다. 이때 우리는 간선의 용량의 최솟값을 구하고자 한다. 간선의 용량을 1부터 10000까지 차례대로 설정하면 시간이 오래 걸리므로, 이분 탐색을 통해 용량을 설정해 가면서 값을 구하면 된다. 숫자판에..

알고리즘/baekjoon 2024. 7. 4. 21:56

1.기존 '17412번: 도시 왕복하기 1' 문제와 비슷하지만, 두 가지가 다르다.- 간선이 단방향에서 양방향으로 바뀌었다.- 본래는 간선의 중복 방문이 불가능했지만, 여기서는 정점의 중복 방문이 불가능하다. 정점의 중복 방문을 어떻게 처리해야 할까? 정점을 용량이 1인 간선으로 만들어 버리면 된다. 예를 들어 정점 \(u\)를 간선으로 만들기 위해서는 \(u+N\)이라는 새로운 정점을 만들고 두 정점을 간선 (\(u, u+N)\)로 이으면 된다. \(u\)와 연결된 정점들은 전부 \(u+N\)에 이어주면 된다. 이렇게 하면 \(u+N\)을 단 한 번만 방문할 수밖게 없게 되므로 정점의 중복 방문을 해결할 수 있다. 간선이 양방향이기에, 간선의 용량 초기화를 쉽게 하기 위해 인접 행렬을 사용하였다.\(s..

알고리즘/baekjoon 2024. 6. 30. 14:14

1.쥐가 전부 구멍에 들어갈 수 있는지에 따라 답을 출력하는 문제이다. 일단  쥐를 최대한 많이 구멍에 들어가게 해야 하므로, 구멍에 들어가는 쥐의 수를 하나의 유량으로 생각하여 최대 유량 문제로 바꿔 풀어보자. 먼저 쥐들과 구멍들을 하나의 간선으로 연결한다. 간선의 용량은 당연히 \(1\)이 될 것이다.\(source\)와 쥐들을 간선으로 연결할 때도 간선의 용량은 당연히 \(1\)이 된다.구멍들과 \(sink\)를 간선으로 연결해 보자. 각 구멍에 들어갈 수 있는 쥐의 수는 \(k\)이므로, 간선의 용량은 \(k\)가 된다. 이 정보들을 종합해 그래프를 구현한 후, 최대 유량 알고리즘을 적용하면 문제를 풀 수 있다. 2.문제는 어떤 쥐들과 구멍들을 간선으로 연결할 지 정하는 것이다. 쥐와 구멍의 좌표..

알고리즘/baekjoon 2024. 6. 30. 10:17