[1671] 상어의 저녁식사

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

이분매칭으로 문제를 해결했습니다.

문제해결방법

1. 인풋으로 들어온 상어의 능력치 별로 간선을 만들어줍니다.

a가 b를 먹을 수 있다면 a의 간선에 b를 넣어줍니다.

이 문제의 핵심은 a==b인 경우입니다.(세 개의 능력치가 같은 경우)

이게 왜 중요하냐면

a가 b를 먹었는데

밑에서 b가 a를 또 먹을 수 있기 때문에 이것을 방지해야합니다.

가장 간단한 방법으로(사실 다른 방법따위 모름) 인덱스가 a < b인 경우에만 먹을 수 있게 하면 됩니다.(물론 같은경우에만)

이렇게 되면 a와 b가 능력치가 같을경우 a를 처리할떄 b를 먹을 것이고 b를 처리할 때는 a > b 이므로 먹을 수 없습니다.

2. 간선을 만든 후 상어는 각각 두마리씩 먹을 수 있습니다. 그러므로 한번 처리할떄 두번씩 먹어줍니다 

제가 계속 실수 했던 부분이

visit을 초기화안하고 먹고 또먹었습니다.

이렇게

    for (int i = 0; i < n; i++) {
        memset(visit, 0, sizeof(visit));
        f(i);
        memset(visit, 0, sizeof(visit));
        f(i);
    }

이렇게 멤셋을 두번해줘야합니다!!!

이유는 아래의 예시를 보면서 설명하겠습니다.

이 그림은 현재

1번이 1번과 2번을 매칭했을 때

2번이 1번을 뺏어서 1번이 3번과 매칭된 상황입니다.

2번이 1번을 뺏으면서 visit[1]은 방문한 상태가 되겠죠??

근데 visit초기화를 안하면

2번이  2번에 매칭을 시도하면서 1번으로 들어가서 1-2를 미뤄내고 4번에 연결되어야하는데(1과 4사이에 선이 있다고 가정)

이미 방문했기 때문에 그냥 넘어가버리게 되죠!@

이게 핵심입니당!!

3. 마지막으로 B배열이 -1인 것을 카운트하여 출력하면 정답입니다.(-1라는 것은 매칭이 안된 것이므로 안죽음)

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
 
#define ll long long
#define INF 987654321
#define MOD 1000000
#define MAX_SIZE 1000
 
using namespace std;
 
int B[MAX_SIZE];
bool visit[MAX_SIZE];
vector<int> edge[MAX_SIZE];
 
int sharkSize[MAX_SIZE];
int sharkIntel[MAX_SIZE];
int sharkSpeed[MAX_SIZE];
 
int n;
 
int eat(int a, int b) {
    int ret = 0;
    if (sharkSize[a] < sharkSize[b]) return 0;
    else if(sharkSize[a] == sharkSize[b]) ret++;
    if (sharkIntel[a] < sharkIntel[b]) return 0;
    else if (sharkIntel[a] == sharkIntel[b]) ret++;
    if (sharkSpeed[a] < sharkSpeed[b]) return 0;
    else if (sharkSpeed[a] == sharkSpeed[b]) ret++;
 
    if (ret == 3) return 2;
    return 1;
}
 
bool f(int from) {
    visit[from] = 1;
 
    for (int i = 0; i < edge[from].size(); i++) {
        int to = edge[from][i];
        if (B[to] == -1 || !visit[B[to]] && f(B[to])) {
            B[to] = from;
            return 1;
        }
    }
 
    return 0;
}
 
 
int main() {
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &sharkSize[i], &sharkIntel[i], &sharkSpeed[i]);
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int eatFlag = eat(i, j);
 
            if (eatFlag == 1) edge[i].push_back(j); //먹을 수 있는경우
            else if (eatFlag == 2 && i < j) edge[i].push_back(j); // 능력치가 같은 경우
        }
    }
 
    memset(B, -1, sizeof(B));
    
    for (int i = 0; i < n; i++) {
        memset(visit, 0, sizeof(visit));
        f(i);
        memset(visit, 0, sizeof(visit));
        f(i);
    }
 
    int ret = 0;
    for (int i = 0; i < n; i++) if (B[i] == -1) ret++;
    printf("%d", ret);
 
    return 0;
}