백준 11377 - 열혈 강호 3(C++)

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

11377번: 열혈강호 3

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

해당 문제에서 응용된 문제입니다. https://junseok.tistory.com/339

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

한명이 한개의 일만 할 수 있지만, K명은 2개를 할 수 있습니다.

복잡해 보이는 문제처럼 보이지만, 쉽게 생각하면 이분매칭 + K번까지만 이분매칭 이라고 생각할 수 있습니다.

 

따라서, 1번 이분매칭을 전체적으로 확인한 뒤, 이분매칭을 한번 더 하는데 매칭이 K번 되는 순간 끝내주면 됩니다.

 

 

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

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>
#include <map>
#define LL long long
#define pp pair<int, int>
#define F first
#define S second

using namespace std;

int N, M, K;
vector<int> Match[1011];
vector<int> a_match, b_match;
bool check[1011];

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

void solve(){
    a_match = vector<int>(N+1, -1);
    b_match = vector<int>(M+1, -1);
    int size = 0, cnt = 0;
    for(int i = 1; i <= N; i++){
        memset(check, false, sizeof(check));
        if(dfs(i)) size++;
    }
    for(int i = 1; i <= N; i++){
        memset(check, false, sizeof(check));
        if(dfs(i)){
            size++;
            cnt++;
        }
        if(cnt == K) break;
    }
    cout << size;
}

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

 

 

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