백준 11375번: 열혈강호 (C++)

접근

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

11375번: 열혈강호

이전에 풀었던 돌멩이 제거하는 문제와 같은 방식의 네트워크플로우 최대이분매칭을 이용한 문제였다.

https://ca.ramel.be/248

백준 1867번: 돌멩이 제거 (C++)

코드

#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

#define endl '\n'
#define MAX_N 1001

int N, K, ans;
int visited[MAX_N];
int bm[MAX_N];
vector<vector<int>> grid(MAX_N);

int dfs(int now) {
    if (visited[now]) return 0;
    visited[now] = 1;
    for (int next : grid[now]) {
        if (bm[next] == 0 || dfs(bm[next])) {
            bm[next] = now;
            return 1;
        }
    }
    return 0;
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        int tn;
        cin >> tn;
        for (int j = 0; j < tn; j++) {
            int work;
            cin >> work;
            grid[i].push_back(work);
        }
    }
    for (int i = 1; i <= N; i++) {
        memset(visited, 0, sizeof(visited));
        if (dfs(i)) ans++;
    }

    cout << ans << endl;

    return 0;
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!