[BaekJoon][11375] 열혈강호

BAEKJOON ONLINE JUDGE

11375 열혈강호

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

열혈강호 시리즈 1

네트워크 플로우 중 이분 매칭 문제

1. C

#include <stdio.h>
 
int person[1001][1001];
int visit[1001];
int work[1001];
 
int bmatch(int p)
{
    int i, w;
 
    if (visit[p])    return 0;
    visit[p] = 1;
 
    for (i = 1; i <= person[p][0]; i++) {
        w = person[p][i];
 
        if (!work[w] || bmatch(work[w])) {
            work[w] = p;
            return 1;
        }
    }
    return 0;
}
 
int main()
{
    int n, m;
    int i, j;
    int ans = 0;
 
    scanf("%d %d", &n, &m);
 
    for (i = 1; i <= n; i++) {
        scanf("%d", &person[i][0]);
 
        for (j = 1; j <= person[i][0]; j++)    {
            scanf("%d", &person[i][j]);
        }
 
        for (j = 1; j <= n; j++)    visit[j] = 0;
        ans += bmatch(i);
    }
 
    printf("%d\n", ans);
 
    return 0;
}

2. C++

#include <cstdio>
#include <vector>
using namespace std;
 
vector<int> person[1001];
bool visit[1001];
int work[1001];
 
int bmatch(int p)
{
    int i, w;
 
    if (visit[p])    return 0;
    visit[p] = true;
 
    for (i = 0; i < person[p].size(); i++) {
        w = person[p][i];
 
        if (!work[w] || bmatch(work[w])) {
            work[w] = p;
            return 1;
        }
    }
    return 0;
}
 
int main()
{
    int n, m;
    int cnt, num;
    int i, j;
    int ans = 0;
 
    scanf("%d %d", &n, &m);
 
    for (i = 1; i <= n; i++) {
        scanf("%d", &cnt);
 
        while (cnt--) {
            scanf("%d", &num);
            person[i].push_back(num);
        }
 
        for (j = 1; j <= n; j++)    visit[j] = false;
        ans += bmatch(i);
    }
 
    printf("%d\n", ans);
 
    return 0;
}