(알고리즘) 이분 도의 최대 일치 (헝가리 알고리즘)

먼저 다음 2 분 도의 개념 을 말 해 보 자. 2 분 도 는 그림 이 두 개의 점 집합 X 와 Y 로 나 눌 수 있다 는 것 을 말한다. 그러면 임의의 한 변 의 두 점 은 서로 다른 점 집합 에 속한다. 즉, 임의의 한 변 의 한 점 은 X 에 있 고 다른 한 점 은 Y 에 있다 는 것 이다.그리고 같은 점 이 집 중 된 임 의 점 사 이 는 끝 이 없 는 것 이 고 이런 성질 을 만족 시 키 는 그림 은 바로 이분 도 이다.
       매 칭 이란 주어진 2 분 그림 G 의 한 변 의 부분 집합 으로 구 성 된 집합 M 을 말 합 니 다. M 의 임 의 두 변 이 모두 공공 정점 이 없 으 면 M 은 하나의 매 칭 이 라 고 합 니 다.그러면 일치 하 는 변 수 를 가장 많이 포함 하 는 일치 가 가장 큰 일치 입 니 다.
       다음은 헝가리 알고리즘 이 어떻게 이분 도의 가장 큰 일치 성 을 구 해 냈 는 지 말씀 드 리 겠 습 니 다.
       헝가리 알고리즘 은 지속 적 으로 확대 경 로 를 찾 아 일치 하 는 집중 적 인 변 수 를 확대 하 는 것 입 니 다. 우 리 는 왼쪽 점 집합 의 모든 점 에 대해 확대 경 로 를 찾 습 니 다. 확대 경 로 를 찾 지 못 할 때 까지 이 럴 때 일치 하 는 것 이 가장 큰 일치 입 니 다.
       헝가리 알고리즘 의 기본 사상 은 바로 이렇다. 구체 적 으로 이해 하려 면 스스로 그림 을 그 려 서 이해 하면 되 고 이해 하기 쉽다.다음은 헝가리 알고리즘 이 어떻게 이 루어 졌 는 지 말씀 드 리 겠 습 니 다.
       우선 우 리 는 2 분 도 를 구축 해 야 한다. 이것 은 너 에 게 달 려 있다.그 다음 에 확장 경 로 를 찾기 위해 서 는 match [i] 가 오른쪽 점 집합 i 의 일치 하 는 왼쪽 점 을 표시 해 야 합 니 다. - 1 이 라면 일치 하 는 점 을 찾 지 못 했 음 을 나타 냅 니 다.이 배열 은 우리 가 확장 경 로 를 찾 을 때 매우 중요 하 다.
        그 다음 에 저 희 는 vis 배열 이 필요 합 니 다. 확장 경 로 를 찾 을 때마다 왼쪽 에 있 는 점 이 방문 되 었 는 지 여 부 를 표시 합 니 다. 이것 은 같은 점 을 반복 해서 찾 는 것 을 방지 하기 위해 서 입 니 다.
        우리 가 확장 경 로 를 다시 찾 을 때 만약 에 점 의 match [i] = - 1 이 있 으 면 우 리 는 확장 경 로 를 찾 아 1 로 돌아 갑 니 다.그렇지 않 으 면 우 리 는 계속 찾 아서 match [i] 에 대해 dfs 를 진행 합 니 다. 만약 에 최종 적 으로 확대 경 로 를 찾 지 못 하면 0 으로 돌아 가 확대 경 로 를 찾 지 못 했다 는 것 을 표시 할 수 밖 에 없습니다.
       이 사상 을 바탕 으로 저 는 POJ 에 있 는 2239 문제 의 코드 를 붙 였 습 니 다. 헝가리 알고리즘 은 대체적으로 차이 가 많 지 않 습 니 다. 필요 한 것 이 있 으 면 참고 하 셔 도 됩 니 다.하하 -

#include 
#include 
#include 
#define LMAX 310
#define RMAX 90
int edge[LMAX][RMAX];
int vis[RMAX],match[RMAX];
int RN;//        ，       


int dfs(int i)
{
    int j;
    for(j=1;j<=RN;j++)
    {
        if(edge[i][j]&&vis[j]==0)
        {
            vis[j]=1;
            if(match[j]==-1)
            {
                match[j]=i;
                return 1;
            }
            else
            {
                if(dfs(match[j]))
                {
                    match[j]=i;
                    return 1;
                }
            }
        }
    }
    return 0;
}

int solve(int LN)
{
    memset(match,-1,sizeof(match));
    int i,sum=0;
    for(i=1;i<=LN;i++)
    {
            memset(vis,0,sizeof(vis));
            if(dfs(i))
                sum++;
    }
    return sum;
}

int main()
{
    int n,t;
    int i;
    int a,b;
    RN=7*12;
//    freopen("data.txt","r",stdin);
    while(scanf("%d",&n)!=EOF)
    {
        memset(edge,0,sizeof(edge));
        for(i=1;i<=n;i++)
        {
            scanf("%d",&t);
            while(t--)
            {
                scanf("%d %d",&a,&b);
                edge[i][(a-1)*12+b]=1;
            }
        }

        printf("%d
",solve(n));

    }
    return 0;
}