백준 14433 - 한조 대기 중(C++)

문제 링크입니다. https://www.acmicpc.net/problem/14433

14433번: 한조 대기 중

이분 매칭을 이용하는 문제입니다.

해당 문제와 같은 방법으로 푸는 문제입니다. 자세한 설명은 링크를 참고해주세요

https://junseok.tistory.com/339

백준 11375 - 열혈강호(C++)

 

해당 문제에서 추가할 점은 팀이 2개라서 이분 매칭을 2번 해야된다는 것입니다.

코드에서 a_match, b_match, check는 값을 초기화를 해주기에 재사용해도 괜찮습니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#define INF 987654321

using namespace std;

int N, M, K1, K2;
vector<int> Match[311][2];
vector<int> a_match, b_match;
bool check[311];
int ans[2];

bool dfs(int start, int cnt){
    if(check[start]) return false;
    check[start] = true;
    for(int i = 0; i < Match[start][cnt].size(); i++){
        int x = Match[start][cnt][i];
        if(b_match[x] == -1 || dfs(b_match[x], cnt)){
            a_match[start] = x;
            b_match[x] = start;
            return true;
        }
    }
    return false;
}

void solve(){
    for(int k = 0; k < 2; k++){
        a_match = vector<int>(N+1, -1);
        b_match = vector<int>(M+1, -1);
        for(int i = 1; i <= N; i++){
            memset(check, false, sizeof(check));
            if(dfs(i, k)) ans[k]++;
        }
    }
    if(ans[0] < ans[1]) cout << "네 다음 힐딱이";
    else cout << "그만 알아보자";
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M >> K1 >> K2;
    for(int i = 1; i <= K1; i++){
        int x, y;
        cin >> x >> y;
        Match[x][0].push_back(y);
    }
    for(int i = 1; i <= K2; i++){
        int x, y;
        cin >> x >> y;
        Match[x][1].push_back(y);
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요