[C++] 과제 1 - Flow Network 응용

제출은 .c/.cpp/.java 파일 하나만 제출해주세요.

 

a명의 사람과 b개의 일자리가 있다.  i번째 사람이 j번째 일을 할 수 있다면 (1 <= i <= a, 1 <= j <= b) 에지 (i, j)로 표시한다. 이런 에지가 n개 있다. 한 사람이 한 개의 일만 할 수 있고, 한 일은 한 사람에게만 줄 수 있다면 이 조건을 만족하게 가장 많이 일자리를 줄 수 있는 개수를 구하는 프로그램을 작성하시오.

 

입력 

표준 입력으로 입력을 받는다. 첫 줄에는 사람의 수 a와 일자리의 수 b, 사람과 일자리를 잇는 에지의 수 n이 주어진다. a, b는 모두 1 이상 100 이하이다. n은 1 이상 a*b 이하이다.  

다음 n 줄에는 사람 i가 일 j를 할 수 있다는 정보를 나타내는 두 정수 i와 j가 사이에 공백을 두고 주어진다. 

 

출력 

사람과 일자리를 가장 많이 이어줄 수 있는 경우의 수를 출력한다. 

 

예제 입력 1

3 3 3

1 3

2 3

3 3

예제 출력 1

1 

 

예제 입력 2

3 3 3 

1 2 

2 3 

3 1 

예제 출력 2

3

 

예제 입력 3

5 6 10

1 1

1 2

2 1

2 3

2 4

3 5

4 2

4 6

5 5

5 6

예제 출력 3

5

 

#include <iostream>
#include <memory.h>
#define M 100
#define N 100

using namespace std;

// 0과 1로 flow의 에지 가중치 설정
bool DFS(bool flowGraph[M][N], int person, bool seen[], int match[])
{
    for (int v = 0; v < N; v++) {
        if (flowGraph[person][v] && seen[v] == false) {
            // 이 사람이 v일을 할 수 있고, v일을 방문했다면 true
            seen[v] = true;
            // v일이 아무에게도 매칭되지 않은 경우 or 매칭된 사람이 v말고 다른 일도 가능한 경우
            if (match[v] < 0 || DFS(flowGraph, match[v], seen, match) == true) {
                match[v] = person;
                return true;  // 다음 함수호출 시, v일을 다시 매치하지 않을 것임
            }
        }
    }
    return false;
}

int maxMatch(bool flowGraph[M][N])
{
    int match[N];  // v일에 대해 매칭된 사람 저장, 아무도 매칭되지 않았다면 -1 저장
    memset(match, -1, sizeof(match));
    int result = 0;  // 매칭 결과 count
    for (int p = 0; p < M; p++)
    {
        bool seen[N];
        // 다음 사람을 위해 방문하지 않은 상태로 초기화
        memset(seen, 0, sizeof(seen));

        if (DFS(flowGraph, p, seen, match))
            result++;
    }
    return result;
}

int main()
{
    int a, b, n = 0;
    cin >> a >> b >> n;

    bool flowGraph[M][N] = {};
    int person, job = 0;

    for (int check = 0; check < n; check++) {
        cin >> person >> job;
        flowGraph[person - 1][job - 1] = 1;
    }
    cout << maxMatch(flowGraph);

    return 0;
}

 

https://www.geeksforgeeks.org/maximum-bipartite-matching/

Maximum Bipartite Matching - GeeksforGeeks

 

비슷한 문제

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

11375번: 열혈강호

 

점수 10/10