MathTrauma

문제 링크 : https://www.acmicpc.net/problem/11495 11495번: 격자 0 만들기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n과 m (2 ≤ n, m ≤ 50)이 주어지며, n은 격자의 행 개수, m은 격자의 열 개수를 나타낸다. 그 다음 n개의 줄에 각각 www.acmicpc.net 1X2 혹은 2X1 타일로 덮는 문제처럼 생각하자. 이 타일들은 좌표 (i , j) 에 대해서 i+j 가 짝수인 것 하나과 홀수인 것 하나를 덮는다. (여기서는 타일들이 곂쳐지게 덮어도 된다.) i+j 가 짝수인 것(짝수 노드)들을 기준으로 타일들을 덮으면, i+j 가 홀수인 것(홀수 노드)들 중 하나가 얼떨결에 같이 덮힌다. 짝수 노드의 값을 1 줄이면..

문제 링크 : https://www.acmicpc.net/problem/11409 11409번: 열혈강호 6 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각의 www.acmicpc.net Min-Cost Max-Flow 의 전형적인 문제이니 문제보다 알고리즘의 정당성에 초점을 맞추어 보자. 먼저 코드를 둘러본다. #include using namespace std; struct MCMF{ struct edge{ int to, cst, cap, rev; }; int sz, Src, Ter; vector adj; vector cst, prv, rIdx; MC..

문제 링크 : https://www.acmicpc.net/problem/1420 1420번: 학교 가지마! 첫째 줄에 도시의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 100) 둘째 줄부터 N개의 줄에 도시의 모양이 주어진다. 비어있으면 점('.'), 벽은 '#', 도현이의 위치는 K, 학교의 위치는 H이다. www.acmicpc.net 출발 정점(도현이의 위치)이나 도착 정점(학교)의 주변을 벽으로 막으면... 맵 모양에 관계없이 답은 4 이하임을 알 수 있다. 따라서 등교를 막을 수 없는 경우를 체크할 때, 유량이 4를 초과하는 것을 이용할 수 있다. 하여간 4 이하인 값 찾기 위해 '유량 네트워크'를 써야 하다니? 다른 방법이 없을까 생각해 보아야겠다. 문제로 돌아가서 어떻게 ..

모델링만 정리하자. 첫 줄은 사람수 n, 서점 수 m 이 주어진다. 출발 노드는 0, 도착 노드는 n+m+1 으로 둔다. (따라서 노드 개수는 n+m+2 ) (1) 다음 행에 사람에 대한 정보가 주어진다. 1 부터 n 까지는 사람에 해당되는 노드 번호로 정했다. 출발 노드로부터 이 노드들에 '비용' 0 이고 간선 '용량'은 $a_i$ 인 간선을 연결. (2) 다음 행(3행)에 서점에 대한 정보가 주어진다. n+1 부터 n+m 까지는 서점을 나타낸다. 비용은 0 이고 용량은 $b_i$ 인 간선을 도착 노드에 연결. (3) 뒤 따르는 m 개의 행에는 서점에서 각 사람(1~n)에게 배송할 때의 비용을 알려준다. 주어지는 정보가 모델링의 순서와 바뀌어서 i 와 j 의 위치에 주의하자. mcmf.link(..

문제 링크 : https://www.acmicpc.net/problem/2316 2316번: 도시 왕복하기 2 N개의 도시가 P개의 양방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 오가며 워해머를 한다. 성실한 이석원은 두 도시 사이를 최대한 많이 왔다 갔다 하려 하는데, 이때 한 번 방 www.acmicpc.net 정점을 한 번만 사용할 수 있다. 정점을 입력 정점과 출력 정점으로 분리하고 둘 사이의 capacity=1 로 둔다. 정점 u 로 들어온 flow 는 u 의 출력 정점인 u+n 까지 기껏해야 1 의 용량을 가지는 간선을 이용하게 된다. 즉, 최대 한 번 이용할 수 있다는 뜻이다. 문제에서 간선 입력 u, v 는 u+n 에서 v 로 그리고 역간선은 v+n, u 로 연결하면 ..

문제 링크 : https://www.acmicpc.net/problem/11377 11377번: 열혈강호 3 첫째 줄에 직원의 수 N과 일의 개수 M, 일을 2개할 수 있는 직원의 수 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있 www.acmicpc.net Max-Flow 관련해서 머리 속에서 raw flow 와 net flow 이 뒤섞여서 헤맸던 과거를 떠올리며... 할 일도 없는데 Push Relabel Algorithm 을 공부해 두자. Max-Flow Min-Cut 정리의 한줄 요약 중간 과정에서 어떤 방식으로 flow를 흘려도 max flow에 도달하지 못한 상황에서는 augment ..