티스토리 뷰

Algorithm

[백준 11375] 열혈강호

devbelly 2020. 7. 26. 13:45

문제

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

 

알고리즘

이분매칭

 

풀이

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

 

코드

#include <bits/stdc++.h>
#include <unordered_set>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

int N, M,cnt,what;
int match[1001];
bool visited[1001];
vector<vector<int>> adj;

bool dfs(int here) {
    visited[here] = true;
    for (auto there : adj[here]) {
        int u = match[there];
        if (!u || !visited[u] && dfs(u)) {
            match[there] = here;
            return true;
        }
    }
    return false;
}

int bipartite_matching() {
    int ret = 0;
    REP(i, N) {
        memset(visited, 0, sizeof(visited));
        if (dfs(i)) ++ret;
    }
    return ret;
}

int main() {
    FAST;
    cin >> N >> M;
    adj.resize(N + 1);
    REP(i, N) {
        cin >> cnt;
        while (cnt--) {
            cin >> what;
            adj[i].emplace_back(what);
        }
    }
    cout << bipartite_matching();

    return 0;
}

'Algorithm' 카테고리의 다른 글

[백준 11376] 열혈강호 2  (0) 2020.07.28
[백준 10747] Censoring  (0) 2020.07.28
[백준 5446] 용량 부족  (0) 2020.07.24
[백준 3080] 아름다운 이름  (0) 2020.07.21
[백준 9249] 최장 공통 부분 문자열  (0) 2020.07.20
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/07   »
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31
글 보관함