[11377번] 열혈강호 3

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 이분 매칭

2. 정렬

열혈강호 시리즈 문제가 상당히 재미있는 문제인 듯 하다.

부분적으로 2개의 일을 할 수 있는 직원 수가 주어진다.

이 직원은 누가 될지 모르는 상황이지만 생각해보면 결국 greedy방식으로 가장 일을 많이 담당하는 사람이

2개의 일을 맡도록 하면 된다.

결국 입력이 주어질 때 일의 개수를 기준으로 내림차순 정렬하여 그 사람이 2개의 일을 하도록 만들면 된다.

결국 열혈강호 2(https://www.acmicpc.net/problem/11376)를 조금 더 응용하여 풀면 해결 할 수 있는 문제이다.

조금 더 코드를 분석해 보자면 다음과 같다.

pair<int, int> pii[1001] 페어가 추가되었고, first에는 일의 개수를, second에는 그 사람의 번호를 넣어준다.

그리고 first를 기준으로 내림차순 정렬을 하고, 이분 탐색을 시작한다.

열혈강호 2까지는 dfs(start)라고 지정하였지만 여기서는 pair를 쓰고있기에 dfs(pii[start].second)를 이용한다.

이 의미는 현재 first를 기준으로 내림차순 정렬이 되어있기에 pii[start]의 사람의 번호를 가져와야 하는 상황이다.

그리고 아래 if(start < k)의 의미는 2개의 일을 할 수있는 사람이 k명이니 

start가 0, 1, .. k - 1인 사람이 2개의 일을 할 수 있다는 의미이다. 이 사람들에 대해서는 이분 매칭을 한번 더 시켜준다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, m, k;
 
// adj[i][j] = Ai와 Bj가 연결되어 있는가?
bool adj[1001][1001];
 
// 정렬에 이용할 pair
pair<int, int> pii[1001];
 
// 각 정점에 매칭된 상대 정점의 번호를 지정한다.
vector<int> aMatch, bMatch;
 
// dfs()의 방문 여부
vector<bool> visited;
 
bool dfs(int here)
{
    if (visited[here])
        return false;
 
    visited[here] = true;
 
    for (int there = 0; there < m; there++)
    {
        // adj가 존재하면
        if (adj[here][there])
        {
            // bMatch에 아직 매치가 안되있거나,
            // 매칭 되어있다면 dfs를 통해 aMatch의 연결 된 것을 재 탐색 시킨다.
            if (bMatch[there] == -1 || dfs(bMatch[there]))
            {
                aMatch[here] = there;
                bMatch[there] = here;
 
                return true;
            }
        }
    }
    return false;
}
 
// 할 수 있는 일의 개수를 기준으로 내림차순 정렬
bool comp(const pair<int, int> &a, const pair<int, int> &b)
{
    return a.first > b.first;
}
 
int main()
{
    int size = 0;
    scanf("%d %d %d", &n, &m, &k);
 
    for (int i = 0; i < n; i++)
    {
        int cnt;
        scanf("%d", &cnt);
 
        pii[i].first = cnt;
        pii[i].second = i;
 
        for (int j = 0; j < cnt; j++)
        {
            int pos;
            scanf("%d", &pos);
 
            adj[i][pos - 1] = true;
        }
    }
 
    sort(pii, pii + n, comp);
 
    aMatch = vector<int>(n, -1);
    bMatch = vector<int>(m, -1);
 
    for (int start = 0; start < n; start++)
    {
        visited = vector<bool>(n, false);
 
        // 깊이 우선 탐색을 이용해 start에서 시작하는 증가 경로를 찾는다.
        if (dfs(pii[start].second))
            size++; 
 
        if(start < k)
        {
            visited = vector<bool>(n, false);
 
            if (dfs(pii[start].second))
                size++;
        }
    }
 
    cout << size;
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>