Bipartite Matching (이분 매칭)

코드

#include <stdio.h>
#include <vector>
#define MAX_V 1010

using namespace std;

int A[MAX_V], B[MAX_V];
vector<int> adj[MAX_V];
bool visited[MAX_V];

bool dfs(int a) {
    visited[a] = true;
    for (int b : adj[a])
        if (B[b] == -1 || !visited[B[b]] && dfs(B[b])) {
            B[b] = a;
            A[a] = b;
            return true;
        }
    return false;
}

int main()
{
    int t;

    scanf("%d", &t);
    while (t--) {
        int n, m, i, j, a, b, match = 0;
        scanf("%d%d", &n, &m);
        for (i = 1; i <= m; i++) {
            scanf("%d%d", &a, &b);
            adj[i].clear();
            for (j = a; j <= b; j++)
                adj[i].push_back(j);
        }

        fill(A, A + MAX_V, -1);
        fill(B, B + MAX_V, -1);
        for (i = 1; i <= m; i++) {
            if (A[i] == -1) {
                fill(visited, visited + MAX_V, false);
                if (dfs(i)) match++;
            }
        }

        printf("%d\n", match);
    }

    return 0;
}

책나눠주기 (https://www.acmicpc.net/problem/9576
) 코드입니다.

정리

  • 이분 그래프 : 정점을 두 그룹으로 나눠서, 모든 간선이 서로 다른 두 그룹의 정점을 연결한 그래프
    • 정점의 집합을 검은색과 흰색으로 나누면, 간선은 서로 다른 색의 정점을 연결하고 있다.
    • 두 집합의 대응 관계를 표현하기 위해 사용한다.
  • 포드 풀커슨, DFS, BFS : O(VE)
    • 코드 길이나 메모리, 속도 측면에서 DFS 를 쓴다
  • Hopcroft-Karp Algorithm을 사용하면 O(Sqrt(V) * E) 에 문제를 해결하는 최적화가 가능하다.
  • DFS 방법
    • 처음에는 어떠한 정점도 연결되지 않음
    • 만약 b 가 매칭되어있지 않다면, 매칭을 등록한다.
    • 만약 b 가 매칭되어있다면, b 부터 dfs 를 수행한다. 성공할 경우, 매칭을 등록한다.

관련 문제

참고 자료

results matching ""

    No results matching ""