본문 바로가기

이분 매칭

BOJ)1017 소수 쌍 문제: icpc.me/1017 N개의 수가 주어질 때 주어진 모든 수를 짝을 지을 때 모든 각각의 짝의 합이 소수가 되도록 할 때 첫 번째 수와 매칭 될 수 있는 모든 수를 구하는 문제이다. 어떤 수 a와 b가 서로 다를 경우 a+b가 소수가 되기 위해서는 a와 b가 짝수와 홀수로 나누어져야한다. 즉 우리는 짝수와 홀수로 이분 그래프 형태로 그래프를 모델링 해준 후 이분 매칭을 구해주어 n/2만큼 매칭 될 경우 1번 정점과 매칭 된 정점을 역추적 해주어 답에 넣어준 후 그 간선만 제거하고 다시 이분매칭을 실행함을 반복해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535.. 더보기
BOJ)1867 돌멩이 제거 문제: icpc.me/1867 한 행을 쭉 이동하거나 한 열을 쭉 이동하면서 돌멩이를 치울 때 최소의 이동횟수로 돌멩이를 다 치울 수 있는지 구하는 문제이다. 우리는 x행 y열에 놓인 돌멩이를 x와 y를 연결시켜주는 이분 그래프 형태로 만들어준 뒤 돌멩이를 줍는다는 것은 결국 x와 y를 연결시키는 간선을 포함하는 것이다. 즉 우리는 간선들을 전부 포함시키는 최소한의 정점을 구하면 된다. 즉 최소 버텍스 커버를 구하는 문제로 해석된다. 이분 그래프에서의 최소 버텍스 커버문제는 이분 매칭과 동치이므로 최대매칭을 구해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637#include #include #include #include #.. 더보기
BOJ)11376 열혈강호2 문제: icpc.me/11376 사람 N명과 할일 M명이 있을 때 각 사람이 최대 두개일을 할 수 있을 때의 최대매칭을 구하면 되는 문제이다. 우리는 각 사람에 대해서 이분 매칭을 2번씩 돌려주어 최대매칭을 구해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #include #include #include #define MAX_N 1000using namespace std;vector vt;int b[MAX_N + 1], visited[MAX_N + 1], n, m, x;bool dfs(int here) { if (visited[here])return false; visited[her.. 더보기
이분 매칭(Bipartite Matching) 네트워크 플로우의 개념중에서 이분 그래프(bipartite grape)에서의 최대 유량을 구하는 경우를 이분 매칭이라고 부릅니다. 이분 그래프는 다음과 같은 모양을 띄고 있습니다. 위의 그림에서 파란색 정점과 노란색 정점들 끼리는 어떠한 간선도 존재하지 않습니다. 이렇게 정점을 두 그룹으로 나누었을 때 모든 간선에 연결 된 두 정점이 서로 다른 그룹에 존재하는 그래프를 이분 그래프라고 합니다. 간선의 용량이 전부 1인 이분 그래프에서의 최대 유량을 구하는 문제는 이분 그래프에서의 최대 매칭과 동치입니다. 이분 그래프에서 매칭이라는 말은 서로 다른 그룹에 놓인 두 정점을 짝지어주는 의미이고 우리는 이분 그래프에서 최대 매칭을 최대 유량 알고리즘인 디닉이나 에드몬드 카프 알고리즘을 이용하여 구해줄 수 있겠지.. 더보기
BOJ)5398 틀렸습니다 문제: icpc.me/5398 충돌되는 단어들에 대하여 가로단어와 세로단어로 이루어진 이분 그래프를 형성시켜준 뒤 mincut을 구해주어 모든단어-mincut을 구해주면 되는 문제이다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include #include #include #include using namespace std;int t, h, v, x, y;char a[2001][2001];int c[2001][2001];int check[1001];int backmatch[1001];vector vt;bool dfs(int her.. 더보기
BOJ)14433 한조 대기 중 문제: icpc.me/14433 A팀과 B팀에 각각 N,M의 유저가 원하는 트롤픽의 목록이 주어질 때 트롤픽을 최대로 선택하여 어떤 팀이 이기게 될지 알아보는 문제이다. A팀의 그래프와 B팀의 그래프를 각각 이분매칭에서의 최대매칭을 구해준 뒤 비교해서 답을 출력해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include #include #include #include using namespace std;int n, m, check[5000], backmatch[5000], k1, k2, x, y, r, a;vector vt;vector wt;bool dfs(int here, const.. 더보기

티스토리툴바