bipartite matching 썸네일형 리스트형 BOJ)12843 복수전공 문제: icpc.me/12843 n개의 강의가 주어질 때 서로 다른 학부의 강의면서 강의의 내용이 겹치는 강의는 두 강의중 하나만 수강할 때 최대로 수강할 강의 수를 구하는 문제이다. 내용이 겹치는 두 강의를 서로 연결해준다면 c학부와 s학부로 이루어진 이분 그래프가 나타나게 된다. 이때 이분 그래프에서 최대로 매칭되는 만큼 수업을 더 안들으면 되기 때문에 이분 매칭을 구해준 후 N에서 빼주면 답이 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #include #include #include using namespace std;int n, m, x, y;char .. 더보기 BOJ)1733 등번호 문제: icpc.me/1733 참가자와 등번호들로 이루어진 이분 그래프를 이분매칭하는 문제이다. 이분 매칭의 역추적은 매칭을 시킬 때 배열등에 저장하여 쉽게 할 수 있다. 다만 N이 100만이므로 매칭때마다 memset을 사용할 경우 TL을 볼 수도 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #include #include using namespace std;vector vt;int check[1000100];int backmatch[1000100];int r[1000100];int n, x, y, s;bool dfs(int here) { .. 더보기 이전 1 다음