본문 바로가기

이분 매칭

BOJ)15271 친구 팰린드롬2 문제: icpc.me/15271남자와 여자에 대한 이분 그래프가 형성되므로 이분 매칭으로 최대로 세울 수 있는 친구 수를 구해줄 수 있다.1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #include #include #include using namespace std;int n, m, visited[222], b[222];vector vt;int dfs(int here) { if (visited[here])return false; visited[here] = true; for (auto next : vt[here]) { if (!b[next] || dfs(b[next])) { b[next] = .. 더보기
BOJ)11670 초등 수학 문제: icpc.me/11670n개의 줄에 순서 쌍 a,b가 주어진다. 각 a,b에 대하여 a+b또는a-b또는a*b 에 일치하는 수들이 중복 없이 n개 존재한다면 그 답을 출력하는 문제이다.이 문제는 잘 생각해보면 순서 쌍 a,b와 답이 될 수 있는 후보인 수들의 이분 그래프로 모델링 할 수 있다.따라서 답을 구하기 위하여 이분 매칭을 구해주어 최대 매칭이 n이 된다면 답을 역추적하여 구해주고, n이 안된다면 impossible을 출력하면 된다.12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include #includ.. 더보기
BOJ)10276 Jewelry Exhibition 문제: icpc.me/10276 각 행이나 열에 빛을 발사해서 보석들을 지킬 때 모든 보석들을 지키는 최소한의 빛의 수를 구하는 문제이다. x행 y열의 위치에 존재하는 보석을 x정점과 y정점을 잇는 간선이라고 생각한다면 결국 모든 보석을 지키는건 각 행(정점)들을 몇개 선택하여 모든 간선을 커버하는 문제로 치환되므로 최소 버텍스 커버 문제로 볼 수 있다. 이분 그래프에서의 최소 버텍스 커버 문제는 쾨닉의 정리에 의해 이분 매칭으로 해결할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include #include #include #include using namespace std;int t, n, m,.. 더보기
BOJ)1444 숌 언어 문제:icpc.me/1444 대문자와 소문자가 번갈아 나타나는 문장이 주어질 때 대문자와 소문자로 이루어진 최소 몇개의 단어로 문장을 만들 수 있는지를 출력하는 문제이다. 이 문제는 (대문자,소문자)로 이루어진 단어와 (소문자,대문자)로 이루어진 단어의 이분 그래프로 나타내면 최소 버텍스 커버 문제로 치환하여 해결할 수 있다. 예를들어 AaAbBa라는 단어가 있을 때 Ab라는 정점과 bB라는 정점이 연결되고 bB라는 정점과 Ba라는 정점이 연결될 것이다. 이 연결을 할 수 있게 만드는 정점의 최소수를 구하는 문제이기 때문에 최소 버텍스 커버 문제로 해결 가능한 것이다. 하지만 맨 처음 나오는 Aa라는 단어와 Ba라는 단어는 항상 선택이 강제 되어야하므로 해당 단어와 연결 된 간선들을 모두 제거해준 뒤 그.. 더보기
UVaOJ)12159 Gun Fight 문제:https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3311 N개의 power가 존재하는 점이 주어지고 진영을 가르는 직선을 결정하는 두 점이 주어진다. 두 점으로 부터 진영을 갈라서 수가 적은 진영이 수가 많은 진영을 이기도록 최대한 매칭할 수 있는 수를 출력하는 문제이다. ccw를 이요하여 모든 점의 진영을 구해준 뒤 진영이 적은 쪽에서 진영이 많은 쪽으로 두 점 사이의 거리가 R이하이고 Power가 0이상이고 진영이 적은 쪽의 power가 진영이 많은쪽의 power보다 많은 두 점을 서로 매칭시켜준 뒤 최대매칭을 구해주면 된다. 123456789101112131415161718192021222324.. 더보기
BOJ)1799 비숍 문제: icpc.me/1799 한 지점에 비숍이 세워진다면 그 지점을 통과하는 두개의 대각선에 있는 모든 지점에는 비숍이 세워질 수 없다. 이를 이용하여 왼쪽 아래로 향하는 대각선과 오른쪽 아래로 향하는 대각선을 가르는 정점들에게 각각 대각선의 번호를 매겨준 뒤 두 대각선으로 이루어진 이분 그래프에서의 최대 매칭을 구하는 문제로 변형시켜서 해결할 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586#include #include #include #includ.. 더보기
BOJ)3683 고양이와 개 문제: icpc.me/3683 투표하는 시청자 v명중에서 고양이를 좋아하는 사람과 개를 좋아하는 사람으로 구분시켜 놓은 뒤 의견이 충돌하는 사람끼리 간선을 이어주면 이분그래프가 완성된다. 문제에서 물어보는건 의견충돌이 최소한이 되야하므로 이분 그래프에서의 min cut을 구해주면 된다. 답은 v-min cut이 된다. 이분매칭에서 mincut문제는 이분매칭으로 해결할 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include #include #include #include #include using namespace std;int t, c.. 더보기
BOJ)9577 토렌트 문제: icpc.me/9577 시간마다 시드를 하나씩 받을 수 있고 각 시간에 시드를 받을 수 있는 사람과 각 사람이 받을 수 있는 시드의 종류가 주어졌을 때 시드를 전부 다운 받는 최소 시간을 출력하는 문제이다. 우리는 시간에 대한 정점과 시드에 대한 정점으로 나누어 이분 그래프를 형성해 준 다음 이분 매칭을 시도하는데 시간 정점중 t번째 정점까지 매칭 했을 때 최대매칭이 시드의 수와 일치할 경우 t초가 최단시간이 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include #include #include #include using namespace std;in.. 더보기
BOJ)2787 흔한 수열 문제 문제: icpc.me/2787 구간에 대한 최댓값과 최솟값이 주어질 때 valid한 수열을 만들 수 있는지 여부를 조사하고 가능할 경우 수열을 출력하는 문제이다. 우리는 구간에 대한 최댓값과 최솟값의 정보를 가지고 i번 위치에 올 수없는 값들을 전부 check해준 뒤 쿼리 입력이 끝나면 i번 위치에 올 수 있는 모든 값들을 연결하여 이분매칭을 시켜주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include #include #include #include #define MAX_N 200using namespace std;ve.. 더보기
BOJ)2191 들쥐의 탈출 문제: icpc.me/2191 땅굴에는 한 들쥐만 들어갈 수 있고 s초가 되기 전에 들쥐가 땅굴에 도착하게 되면 잡아먹히지 않을 때 잡아먹히게 되는 들쥐의 최솟값을 출력하는 문제이다. 잡아먹히는 들쥐의 최솟값은 즉 땅굴에 도착하는 들쥐의 최댓값의 여집합이므로 들쥐가 도달할 수 있는 땅굴에 대하여 간선을 연결하여 땅굴/들쥐의 이분 그래프를 형성한 뒤 최대매칭을 구하여 총 들쥐의 수에서 빼주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include #include #include #define MAX_N 100using namespace std;double get.. 더보기