HDU 2063 롤러 코스 터(헝가리 알고리즘)(이분 도 최대 일치)

롤러 코스 터
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 16667 Accepted Submission(s): 7281
Problem Description
RPG 걸 스 는 오늘 여러분 과 함께 놀이 공원 에 놀 러 가 꿈 에 그리 던 롤러 코스 터 를 탈 수 있 게 되 었 습 니 다.그러나 롤러 코스 터 는 한 줄 에 두 개의 좌석 만 있 고 성문 화 되 지 않 은 규칙 도 있다.즉,모든 여자 들 은 반드시 한 명의 남 자 를 찾 아 파트너 가 되 어 그녀 와 함께 타 야 한 다 는 것 이다.그러나 모든 여자 들 은 각자 의 생각 을 가지 고 있 습 니 다.예 를 들 어 Rabbit 는 XHD 나 PQK 와 만 파트너 가 되 고 Grass 는 linle 이나 LL 과 만 파트너 가 되 고 싶 습 니 다.PrincessSnow 은 수역 의 방탕아 나 가짜 쿠 아 와 파트너 가 되 고 싶 습 니 다.경비 문 제 를 고려 해 보스 유 는 파트너 를 찾 은 사람 에 게 만 롤러 코스 터 를 타 게 하기 로 했다.다른 사람들 은 헤헤,아래 에 서서 지 켜 보기 로 했다.똑똑 한 Acmer,최대 몇 쌍 의 그룹 이 롤러 코스 터 를 탈 수 있 는 지 계산 해 주 시 겠 어 요?

Input
데 이 터 를 입력 한 첫 줄 은 세 개의 정수 K,M,N 으로 각각 가능 한 조합 수,여자 의 수,남자 의 수 를 나타 낸다.01<=N 과 M<=500.다음 K 줄 은 줄 마다 두 개의 숫자 가 있 는데 각각 여자 아이 가 남자 Bj 와 파트너 가 되 기 를 원한 다 는 것 을 나타 낸다.마지막 0 입력 종료.

Output
각 조 의 데이터 에 대해 하나의 정 수 를 출력 하면 롤러 코스 터 를 탈 수 있 는 최대 조합 수 를 나타 낸다.

Sample Input

Sample Output

이 문 제 는'헝가리 알고리즘'을 사 용 했 습 니 다.헝가리 는 이 알고리즘 에 대한 소개 가 보통 어렵 습 니 다.저 는'헝가리 알고리즘'을 설명 하 는 글 을 바 꾸 었 습 니 다.아주 좋 습 니 다. 헝가리
코드 는 다음 과 같 습 니 다:

#include<iostream>
#include<cstring>
using namespace std;
int k,m,n;
int match[505][505],use[505],girl[505];
bool dfs(int x)
{
    for(int i=1;i<=n;i++)
    {
        //     ，       
        if(match[x][i]==true&&use[i]==false)
        {
            use[i]=true;//         
            if(girl[i]==0||dfs(girl[i]))
            {
                girl[i]=x;//      
                return true;
            }
        }
    }
    return false;
}
int main()
{
    while(cin>>k,k)
    {
        cin>>m>>n;
        memset(match,0,sizeof(match));
        memset(girl,0,sizeof(girl));
        int x,y;
        for(int i=0;i<k;i++)
        {
            cin>>x>>y;
            match[x][y]=1;
        }
        int ans=0;
        for(int i=1;i<=m;i++)
        {
            memset(use,0,sizeof(use));
            if(dfs(i))
                ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

원탁 문제 HDU 4841 PE...

원탁 문제 Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 466 Ac...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

HDU 2063 롤러 코스 터(헝가리 알고리즘)(이분 도 최대 일치)

좋은 웹페이지 즐겨찾기