티스토리 뷰

백준

백준 소스코드 [C++] 11375 열혈강호

Hani_Levenshtein 2020. 9. 12. 10:09

www.acmicpc.net/problem/11375

 

11375번: 열혈강호

강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각��

www.acmicpc.net

백준 소스코드 [C++] 11375 열혈강호

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
typedef long long ll;
using namespace std;
#define MAX 987654321
int L, R;
#define left_max 1000
#define right_max 1000
bool adj[left_max][right_max];
vector<int> leftmatch, rightmatch;
vector<bool> visited;

bool dfs(int l) {
    if (visited[l]) return false;
    visited[l] = true;
    for (int r = 0;r < R;r++) {
        if (adj[l][r]) {
            if (rightmatch[r] == -1 || dfs(rightmatch[r])) {
                leftmatch[l] = r; rightmatch[r] = l; return true;
            }

        }
    }
    return false;
}

int match() {
   leftmatch = vector<int>(L, -1); rightmatch = vector<int>(R, -1);
    int size = 0;
    for (int l = 0;l < L;l++) {
        visited = vector<bool>(L, false);
        if (dfs(l)) size++;
    }
    return size;
}
int main() {
    cin >> L>>R;
    int t,m;
    for (int i = 0;i < L;i++) {
        cin >> t;
        while (t--) {
            cin >> m;
            adj[i][m-1] = true;
        }
    }
    cout << match();
    return 0;

}
댓글