[1671번] 상어의 저녁식사

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 이분 매칭 :: http://www.crocus.co.kr/499

상어의 저녁식사 또한 이분 매칭 문제이다.

열혈강호2 문제와 똑같은 문제이니 이 문제를 푼다면 열혈강호2 문제도 풀어보길 바란다.

[11376번] 열혈강호 2 :: https://www.acmicpc.net/problem/11376

이 문제의 핵심은 A그룹(잡아먹는 그룹) B그룹(잡아먹히는 그룹)이 있다면

A그룹에서 B그룹으로 최대 두개의 간선을 뻗을 수 있다는 것이다.

즉, 1->2 1->3 2->4가 있다면

1은 2와 3으로 매칭이 가능하고 2는 4와 매칭이 가능하다는 것이다.

그 방식은 이분 매칭에서 dfs를 두번 돌리면 해결된다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <vector>
#include <memory.h>
 
#define MAX_N 1002
 
using namespace std;
 
typedef struct _JAWS_
{
    int size;
    int speed;
    int intel;
}JAWS;
 
int n;
JAWS jaws[MAX_N];
bool adj[MAX_N][MAX_N];
int aMatch[MAX_N];
int bMatch[MAX_N];
 
int visit[MAX_N];
int visitCnt = 1;
 
bool dfs(int a)
{
    if (visit[a] == visitCnt)
        return false;
 
    visit[a] = visitCnt;
    for (int b = 1; b <= n; b++)
    {
        if (adj[a][b])
        {
            if (bMatch[b] == -1 || dfs(bMatch[b]))
            {
                aMatch[a] = b;
                bMatch[b] = a;
 
                 return true;
            }
        }
    }
    return false;
}
int bipartiteMatch()
{
    int size = 0;
 
    memset(aMatch, -1, sizeof(aMatch));
    memset(bMatch, -1, sizeof(bMatch));
 
    for (int a = 1; a <= n; a++)
    {
        visitCnt++;
        size += dfs(a);
        visitCnt++;
        size += dfs(a);
    }
 
    return size;
}
 
int main()
{
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++)
    {
        int size, speed, intel;
        scanf("%d %d %d", &size, &speed, &intel);
 
        jaws[i].size = size;
        jaws[i].speed = speed;
        jaws[i].intel = intel;
    }
 
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
                continue;
 
            if (jaws[i].size == jaws[j].size && jaws[i].speed == jaws[j].speed && jaws[i].intel == jaws[j].intel && i > j)
                continue;
 
            if (jaws[i].size >= jaws[j].size && jaws[i].speed >= jaws[j].speed && jaws[i].intel >= jaws[j].intel)
                adj[i][j] = 1;
        }
    }
 
    int cnt = bipartiteMatch();
 
    printf("%d\n", n - cnt);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>