글 읽기 - 1671 이분매칭문제 잘 모르겠습니다.

josualaurant 9년 전 0

이분 매칭 공부하다가 이 문제 풀게 되었는데요.

그래프는 상어끼리 비교해서 i번째 상어가 j번째 상어를 먹을 수 있으면 bpGraph[i][j]=1 로 뒀고

이분매칭하는 과정에서 한 상어가 두마리까지 먹을 수 있으니까

반복문에서 i번째 상어가 먹을 수 있는 상어와 매칭되는 과정을 두번 씩 반복했습니다.

예외처리는 두 마리 상어가 서로 잡아먹을 수 없으니까 이분매칭이 끝나고 서로 잡아먹는 경우 한마리는 남게 +1해줬고

모든 상어가 서로 잡아먹을 수 있을 때 0이 나올때 1마리가 남게 해줬습니다.

이렇게 푸는 방법 자체가 잘못된건가요?

#include <iostream>
#include <string.h>
using namespace std;
int N, M;

bool bpm(bool bpGraph[1001][1001], int u, bool seen[], int matchR[])
{
    for (int v = 0; v < N; v++)
    {
        if (bpGraph[u][v] && !seen[v])
        {
            seen[v] = true;
            if (matchR[v] < 0 || bpm(bpGraph, matchR[v], seen, matchR))
            {
                matchR[v] = u;
                return true;
            }
        }
    }
    return false;
}

int maxBPM(bool bpGraph[1001][1001])
{
    int matchR[1001];
    
    memset(matchR, -1, sizeof(matchR));
    
    int result = 0;     for (int u = 0; u < M; u++)
    {
        bool seen[1001];
        memset(seen, 0, sizeof(seen));
        
        if (bpm(bpGraph, u, seen, matchR))
            result++;
        if (bpm(bpGraph, u, seen, matchR))
            result++;
    }
    int a=0;
    for(int i=0;i<M;i++){
        if(i==matchR[matchR[i]])
            a++;
    }
    if(result-a/2<N)
        return result-a/2;
    else
        return N-1;
}

bool bpGraph[1001][1001];
typedef struct{
    int b;
    int s;
    int i;
}Shark;
int main()
{
    Shark sh[1001] = { 0, };
    
    int T;
    scanf("%d", &T);
    for (int i = 0; i < T; i++)
        scanf("%d %d %d", &sh[i].b, &sh[i].s, &sh[i].i);
    
    for (int i = 0; i < T; i++){
        for (int j = 0; j < T; j++){
            if (sh[i].b >= sh[j].b&&sh[i].s >= sh[j].s&&sh[i].i >= sh[j].i&&i != j)
                bpGraph[i][j] = 1;

        }
    }
    N = T;
    M = T;
    
    
    cout<<T-maxBPM(bpGraph);
    
    return 0;
}

h0ngjun7 9년 전 0

상어들의 능력치가 같은 경우도 생각해보세요.

josualaurant 9년 전 0

상어들의 능력치가 같은 경우 서로 잡아먹을 수 있어서 그런 경우 +1해주고

전부 능력치가 같아서 다 잡아먹어 0이 나올경우 1 나오게 처리했는데 이 밖에도 능력치가 같은 예외가 있나요?

h0ngjun7 9년 전 1

저 같은 경우에는 상어가 서로 잡아먹는 경우를 방지하기 위해서 index가 작은 애가 큰 애만 먹을 수 있도록 해줬어요. 그것 외에는 없던 걸로 기억해요.

baekjoon 9년 전 0

저도 @hongjun7 처럼 처리했어요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1671 이분매칭문제 잘 모르겠습니다.

josualaurant 9년 전 0

h0ngjun7 9년 전 0

josualaurant 9년 전 0

h0ngjun7 9년 전 1

baekjoon 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말