devbelly

문제 https://www.acmicpc.net/problem/11378 알고리즘 이분매칭 풀이 열혈강호 3과 달라진 점은 한 사람당 최대 두 가지의 일을 할 수 있었던 3번 문제에 반해, 열혈강호 4는 벌점에 따라 한 사람당 최대할 수 있는 일의 수가 달라진다는 점입니다. 비슷하므로 비슷하게 풀어봅시다. 마찬가지로 $N$까지 루프를 한번 돌려 한 사람당 한 가지 일을 매칭해주도록 합시다. 열혈강호 3에선 추가적으로 루프를 한 번만 더 돌려서 한 사람당 최대 두 가지 일을 할 수 있다 라는 점을 구현하였는데, 이 문제에선 추가 매칭이 이루어지지 않을 때까지 루프를 돌립니다. 즉 $K$를 다 사용하거나, 아직 $K$가 남아있지만 더 이상 사람이 일을 할 수 없을 때를 뜻합니다. 시간 복잡도는 $O(K*VE..

문제 https://www.acmicpc.net/problem/11377 알고리즘 이분매칭 풀이 열혈강호 시리즈 세 번째 문제입니다. 열혈강호 2와 같이 한 사람당 최대 두 개의 일을 한다는 점은 같지만 추가 매칭이 최대 K번 가능한 점이 다릅니다. 비슷한 문제이므로, 비슷하게 풀 수 있습니다. $bipartite matching()$에서 $N$까지 루프를 한번 돌려서 한 사람당 한가지 일을 하도록 매칭을 한 후, 다시 루프를 돌며 추가매칭이 K번 이하 이루어졌다면 계속해서 매칭을 해주면 됩니다. 역시 시간 복잡도는 $O(VE)$입니다. 코드 #include #include #define rep(i,n) for(int i=0;i N >> M >> K; adj.resize(N + 1); REP(i, N) ..

문제 https://www.acmicpc.net/problem/11376 알고리즘 이분매칭 풀이 두 가지의 풀이가 있습니다. 1번 풀이는 정점분할입니다. 사람정점 $i$번에 대해 $T(i)$,$F(i)$ 이와 같이 두가지의 정점으로 나눈후 열혈강호 1과 동일하게 풀면 됩니다. 2번 풀이는 사람정점 $i$번에 대해 dfs를 두 번 수행하는 것입니다. 그럼 한 사람당 최대 두가지 일에 매칭이 되어 문제를 해결할 수 있습니다. 코드1 #include #define rep(i,n) for(int i=0;i> v; adj[T(i)].emplace_back(v); adj[F(i)].emplace_back(v); } } cout > M; adj.resize(N + 1); REP(i, N) { cin >> cnt; w..

문제 https://www.acmicpc.net/problem/11375 알고리즘 이분매칭 풀이 존재하는 정점을 두 가지 그룹으로 나누었을 때, 간선의 양 끝점 정점이 서로 다른 그룹에 속해있는 그래프를 이분 그래프라고 하고, 이분 그래프상에서 최대 매칭을 구하는 문제를 이분 매칭이라고 합니다. 기본적인 이분매칭 문제로, 전체적인 구현은 프로그래밍 콘테스트 챌린징의 이분매칭 구현을 참고하였습니다. 핵심인 $dfs$ 함수는 현재 정점(사람)의 간선을 검사하는데 만약 반대 정점(일)이 매칭이 되지 않았거나, 매칭 되었더라도 해당 매칭을 옮길 수 있으면 true를 리턴하게 됩니다. 이로써 최대 매칭에 성공하게 되는 것이죠. 각 정점에 대해 $dfs$를 수행하므로 시간 복잡도는 $O(VE)$입니다. 코드 #in..