백준: 11375, 11376, 11377(이분 매칭, Bipartite Matching)

</br> 선배가 ICPC 문제 보니까 네트워크 플로우 알고리즘이 많이 나온다고 하셔서 공부해 보기로 했다
그 응용 중 하나인 이분 매칭을 정리해 보자

11375: 열혈강호가 정확히 이분 매칭 문제이므로 일단 바로 가자
</br>

11375: 열혈강호

https://www.acmicpc.net/problem/11375

n명이 있고 m개의 일이 있는데, n명이 각 1개 씩 일을 맡아서 할 때 할 수 있는 최대의 일의 수

#include <bits/stdc++.h>

using namespace std;

vector<int> v[1001];
int work[1001];
int visited[1001];

bool dfs(int now){
    visited[now] = 1;

    for(int i = 0; i < v[now].size(); i++){
        int nx = v[now][i];
        if( work[nx] == 0 || (visited[work[nx]] == 0 && dfs(work[nx])) ){
            work[nx] = now;
            return true;
        }
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        int a;
        cin >> a;
        for(int j = 0; j < a; j++){
            int b;
            cin >> b;
            v[i].push_back(b);
        }
    }

    int ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < n; j++){
            visited[j] = 0;
        }
        if( dfs(i) ) ans++;
    }

    cout << ans << endl;

}

벡터 v에 매칭 가능한 애들을 인접 리스트처럼 넣어준다.
그 다음 dfs를 도는데,

1. 만약 현재 애가 갈 수 있는 곳이 비어있거나
2. 그 갈 수 있는 곳을 차지한 애(work[nx])를 dfs(work[nx])로 다른 곳에 넣을 수 있다면 이 자리를 현재 애로 채워 버린다.

이런 식으로 하면 된다 얘는 알고리즘 자체는 생각보다 간단하구나

</br>

11376: 열혈강호 2

https://www.acmicpc.net/problem/11376

n명이 있고 m개의 일이 있는데, n명이 각 2개 씩 일을 맡아서 할 때 할 수 있는 최대의 일의 수

// in main()
    int ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < n; j++){
            visited[j] = 0;
        }
        if( dfs(i) ) ans++;
        for(int j = 0; j < n; j++){
            visited[j] = 0;
        }
        if( dfs(i) ) ans++;
    }

그냥 메인 함수에서 dfs를 두 번 돌려 주면, 그 사람이 할 일을 두 번 찾게 될 거니까 해결된다.

</br>

11377: 열혈강호 3

https://www.acmicpc.net/problem/11377

n명이 있고 m개의 일이 있는데, n명이 각 1개 씩 일을 맡아서 하고 n명 중 k명은 1개 씩 더 맡아서 할 때 할 수 있는 최대의 일의 수

    int ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            visited[j] = 0;
        }
        if( dfs(i) ) ans++;
    }

    int cnt = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            visited[j] = 0;
        }
        if( dfs(i) ){
            ans++;
            cnt++;
        }
        if( cnt == k ) break;
    }
    cout << ans << endl;

이것도 위와 비슷하게, 일단 일을 하나 씩 할당한다.
그리고 k번 더 할당하면 된다.
</br>

이분 매칭

vector<int> v[1001];
int work[1001];
int visited[1001];

bool dfs(int now){
    visited[now] = 1;

    for(int i = 0; i < v[now].size(); i++){
        int nx = v[now][i];
        if( work[nx] == 0 || (visited[work[nx]] == 0 && dfs(work[nx])) ){
            work[nx] = now;
            return true;
        }
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        int a;
        cin >> a;
        for(int j = 0; j < a; j++){
            int b;
            cin >> b;
            v[i].push_back(b);
        }
    }

    int ans = 0;
    for(int i = 1; i <= n; i++){
        for(int k = 0; k < 매칭가능한 최대 개수; k++){
            for(int j = 0; j < n; j++){
                visited[j] = 0;
            }
            if( dfs(i) ) ans++;
        }
    }

    cout << ans << endl;

}

따라서 이분 매칭 코드는 이런 느낌이다
최대 개수에 따라서 맞게 그냥 dfs를 여러 번 해 주면 된다.
</br>

---

쏠쏠한 걸 배웠다
</br>