C++헝가리 알고리즘 구현
헝가리 알고리즘(Hungarian algorithm)은 주로 이분 도와 일치 하 는 문 제 를 해결 하 는 데 사용 되 기 때문에 이분 도 를 먼저 알 아 보 겠 습 니 다.
이분 도(Bipartite graph)는 특수 한 그림 으로 두 부분 으로 나 눌 수 있 으 며 각 부분의 점 은 서로 연결 되 지 않 는 다.아래 그림 은 전형 적 인 이분 도이 다.
위의 이분 도 에서 각 변 의 단점 은 각각 점 집 X 와 Y 에 있 는 것 을 볼 수 있다.헝가리 알고리즘 은 주로 두 가지 문 제 를 해결 하 는 데 사용 된다.이분 도의 최대 일치 수 와 최소 덮어 쓰기 수 를 구 하 는 것 이다.
이렇게 말 하면 너무 추상 적 이어서 우 리 는 지금 실제 문제 에서 출발한다.
질문
위 에서 말 한 것 을 보고 독자 들 이 안개 속 에 있다 고 느 낄 것 이 라 고 믿는다.이것 은 무엇 입 니까?이게 무슨 소 용이 야?그래서 우 리 는 이 2 분 도 를 약간 손발 을 만들어 아래 처럼 만 들 었 다.
현재 보 이 스 와 걸 스 는 각각 두 개의 점 집 으로,그 안 에는 각각 남자 와 여자 가 포 인 트 를 두 고 있 으 며,이들 사이 에는'썸 관계'가 있다 고 밝 혔 다.가장 큰 매 칭 문 제 는 만약 당신 이 홍모 라면 썸 을 타 는 남녀 를 매 칭 할 수 있다 면 얼마나 많은 커 플 이 될 수 있 습 니까?수학 적 표현:2 분 도 에서 공공 점 이 없 는 가장 많은 변 을 찾 을 수 있다)
이제 헝가리 알고리즘 이 어떻게 작 동 하 는 지 살 펴 보 자.
우 리 는 B1 부터(남녀평등,여자 쪽 에서 도 가능)G2 와 썸 을 탄다.그러면 우 리 는 잠시 G2 와 연결 하 자.
B2 를 보면 B2 도 G2 를 좋아 합 니 다.이때 G2 는'명화 유주'가 되 었 습 니 다.(우리 가 생각 했 지만)어떻게 해 야 합 니까?G2 가 현재 배 정 된 남자친구,B1 인 데 B1 은 다른 옵션 이 있 나 요?네,G4,G4 가 아직 배정 되 지 않 았 으 니 B1 에 G4 를 배정 하 겠 습 니 다.
그리고 B3,B3 에 G1 을 직접 맞 추 면 돼 요.문제 없어 요.B4 에 대해 서 는 G4 에 만 반 했 고 G4 는 현재 B1 을 맞 추고 있다.B1 은 G4 말고 G2 도 선택 할 수 있 지만 B1 이 G2 를 선택 하면 G2 의 원 배 B2 는 선택 할 수 없다.우 리 는 한 바퀴 돌 았 는데,B4 는 솔로 가 될 수 밖 에 없다 는 것 을 알 게 되 었 다.불쌍 하 다.사실 한번 도 생각해 본 적 없 는 G3 가 더 불쌍 하 다)
이것 이 바로 헝가리 알고리즘 의 절차 입 니 다.구체 적 인 실현 에 대해 코드 를 살 펴 보 겠 습 니 다.
int M, N; //M, N 、
int Map[MAXM][MAXN]; //
int p[MAXN]; //
bool vis[MAXN]; //
bool match(int i)
{
for (int j = 1; j <= N; ++j)
if (Map[i][j] && !vis[j]) //
{
vis[j] = true; //
if (p[j] == 0 || match(p[j])) // ，
{
p[j] = i; //
return true; //
}
}
return false; // ， ，
}
int Hungarian()
{
int cnt = 0;
for (int i = 1; i <= M; ++i)
{
memset(vis, 0, sizeof(vis)); // vis
if (match(i))
cnt++;
}
return cnt;
}3.가장 작은 덮어 쓰기 문제
또 다른 이분 도 에 관 한 문 제 는 가장 작은 덮어 쓰 기 를 구 하 는 것 이다.우 리 는 가장 적은 점 을 찾 아서 이분 도의 모든 변 에 적어도 한 개의 단점 이 이 점 안에 있 도록 하고 싶다.거꾸로 말 하면 이 점 을 포함 하 는 변 을 삭제 하면 모든 변 을 삭제 할 수 있다 는 것 이다.
이것 은 왜 헝가리 알고리즘 으로 해결 할 수 있 습 니까?네가 만약 내 가 오랫동안 장광설 을 늘 어 놓 으 려 고 한다 면 우 리 는 단지 하나의 정리 가 필요 하 다.
(K ö nig 정리)
2 분 그림 의 최대 일치 수 는 이 그림 의 가장 작은 덮어 쓰기 수 와 같 습 니 다.
자,이 절 은 끝 낼 수 있 습 니 다.우 리 는 수학 을 하 는 것 이 아니 라 증명 할 필요 가 없습니다.그러나 최소 커버 점 집합 을 직관 적 으로 찾 는 방법 을 제공 합 니 다.문제 도 를 보고 왼쪽 에 일치 하지 않 는 성공 점 에서 출발 하여 헝가리 알고리즘 의 절차(즉 보라색 화살표)를 한 번 갑 니 다.모든 왼쪽 에 지나 지 않 은 점 과 오른쪽 에 지나 가 는 점,즉 가장 작은 커버 를 구성 합 니 다.(그림 속 B3,G2,G4)
모든 왼쪽 노드 에 대해 확장 로 를 찾 아 최대 2 분 도 를 한 번 씩 옮 겨 다 니 기 때문에 이 알고리즘 은 시간 복잡 도 는 O(MN)이다.
4.헝가리 알고리즘 의 응용
일부 문 제 는 언뜻 보기 에는 위 에 있 는 남녀 의 짝 짓 기 문제 와 비슷 한 점 이 없 지만 사실은 헝가리 알고리즘 을 사용 할 수 있다.예 를 들 면:
4.1(낙 곡 P1129)[ZJOI 2007]매트릭스 게임
제목 설명
작은 Q 는 매우 총명 한 아이 로 체스 를 제외 하고 컴퓨터 퍼 즐 게임 DD 매트릭스 게임 도 즐겨 한다.매트릭스 게임 은$N× N$흑백 방진 진행(체스 처럼 색깔 만 마음대로).매번 이 행렬 에 대해 두 가지 조작 을 할 수 있 습 니 다.
줄 교환 작업:행렬 의 임의의 두 줄 을 선택 하고 이 두 줄 을 교환 합 니 다.(즉,대응 하 는 칸 의 색 을 교환 합 니 다)
열 교환 작업:행렬 의 임의의 두 열 을 선택 하고 이 두 열 을 교환 합 니 다.(즉,대응 하 는 칸 의 색 을 교환 합 니 다)
게임 의 목 표 는 여러 번 의 조작 을 통 해 방진 의 주 대각선(왼쪽 상단 에서 오른쪽 하단 까지 의 연결선)의 칸 을 모두 검은색 으로 하 는 것 이다.
어떤 관문 에 대해 작은 Q 는 아무리 생각해 도 풀 리 지 않 아서 그 는 이 관문 들 이 근본적으로 풀 리 지 않 는 것 이 아니 냐 고 의심 하기 시작 했다.그래서 소 Q 는 이 관문 들 이 풀 렸 는 지 아 닌 지 를 판단 하기 위해 프로그램 을 쓰기 로 했다.
입력 형식
첫 줄 에는 데 이 터 를 나타 내 는 정수 T 가 포함 되 어 있 습 니 다.
다음은 T 조 데 이 터 를 포함 하고 각 조 의 데이터 첫 번 째 행 위 는 정수 N 으로 방진 의 크기 를 나타 낸다.다음 N 행동 1 개$N× N$의 01 행렬(0 은 흰색,1 은 검은색).
출력 형식
T 줄 포함.각 그룹의 데이터 에 대해 이 관문 이 풀 리 면 Yes 한 줄 을 출력 합 니 다.그렇지 않 으 면 No 줄 을 출력 합 니 다.
우 리 는 행렬 을 이분 도(왼쪽 집합 은 각 줄 을 대표 하고 오른쪽 집합 은 각 열 을 대표 하 며 특정한 위 치 는 1 이면 이 줄 과 이 열 사이 에 가장자리 가 있다)로 전환시킨다.우 리 는 X1 이 Y1,X2 가 Y2 를 연결 할 수 있 도록 일련의 교환 작업 을 진행 하고 싶 습 니 다.
이른바 교환 이 라 고 해서 이름 을 바 꿀 수 있 는 지 상상 할 수 있 습 니 다.우 리 는 현재 이분 도 구조 가 변 하지 않 는 상황 에서 오른쪽 점 의 번 호 를 바 꿀 수 있다.이것 은 교환 효과 와 같다.
그래서 X1,X2...Y1,Y2 와 일일이 대응 하려 면 원래 그림 의 최대 매 칭 수가 4 이면 됩 니 다.(이것 은 조합 수학 에서 서로 다른 대표 학과 의 개념 과 일치한다.코드 는 다음 과 같 습 니 다:
#include <cstdio>
#include <cstring>
int Map[205][205], p[205], vis[205], N, T;
bool match(int i){
for (int j = 1; j <= N; ++j){
if (Map[i][j] && !vis[j]){
vis[j] = 1;
if (p[j] == 0 || match(p[j])){
p[j] = i;
return true;
}
}
}
return false;
}
int Hungarian(){
int cnt = 0;
for (int i = 1; i <= N; ++i){
memset(vis, 0, sizeof(vis));
if (match(i))
cnt++;
}
return cnt;
}
int main(){
scanf("%d", &T);
while (T--){
scanf("%d", &N);
memset(p, 0, sizeof(p));
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= N; ++j)
scanf("%d", &Map[i][j]);
puts(Hungarian() == N ? "Yes" : "No");
}
return 0;
}OIBH 조직의 날 뛰 는 기세 에 직면 하여 코 난 은 외양간 에 깊이 들 어가 허실 을 탐색 하기 로 결정 했다.
그 는 심사숙고 끝 에 OIBH 조직 문 으로 들 어가 기로 결정 했다.
OIBH 조직의 대문 에 신기 한 자물쇠 가 있 습 니 다.
자 물 쇠 는 M*N 칸 으로 구성 되 어 있 으 며,그 중 일부 칸 은 돌출 되 어 있 습 니 다(회색 칸).매번 조작 할 때마다 특정한 줄 이나 특정한 열의 칸 을 누 를 수 있 습 니 다.
코 난 이 조직 이 제한 한 횟수 내 에 모든 칸 을 누 를 수 있다 면 그 는 본사 에 들 어 갈 수 있 을 것 이다.그러나 OIBH 조직 은 채식 을 하지 않 고 그들의 제한 횟수 가 가장 적다.
코 난 이 주어진 자 물 쇠 를 여 는 데 필요 한 최소 횟수 를 계산 할 수 있 도록 도와 주세요.
읽 기/입력:
첫 번 째 줄 은 100 을 넘 지 않 는 정수 N 이 고 M 은 행렬 의 길이 와 폭 을 나타 낸다.
아래 N 줄 의 줄 당 M 개 수 는 0 즉 1 이 아 닌 돌출 격자 이다.
출력/출력:
하나의 정수 에 필요 한 최소 횟수
만약 에 우리 가 사례 의 행렬 을 이분 도 형식 으로 바 꾸 면 다음 과 같다.
한 줄 이나 한 열 을 누 르 면 사실은 어떤 점 과 연 결 된 모든 변 을 지 우 는 것 이다.지금 은 최소한 의 조작 횟수 를 요구 하고 있 습 니 다.생각해 보 세 요.이것 은 가장 작은 커버 수 를 구 하 는 것 이 아 닙 니까?그 러 니까 헝가리 알고리즘 을 직접 끼 워 넣 으 면 돼.부호 약.
4.3,(TYVJ P1035)바둑판 덮어 쓰기
설명 설명
nn(n<=100)의 체스 판 을 제 시 했 는데 그 중 일부 점 이 삭제 되 었 습 니 다.12 의 도미 노 골 패 를 사용 하여 감 출 수 있 는 지 물 었 습 니 다.
입력 형식 입력 형식
첫 번 째 행동 n,m(m 개 삭 제 된 칸 표시)
두 번 째 줄 에서 m+1 행위 x,y 까지 각각 칸 이 있 는 위 치 를 삭제 하 는 것 을 나타 낸다.
x 는 x 행
y 는 y 열 이다.
출력 형식 출력 형식
최대 덮어 쓰기 칸 수
전형 적 인 도미 노 커버 문 제 는 모두 가 잘 알 고 있다.우 리 는 바둑판 을 염색 했다.도미 노 골패 마다 흰색 칸 과 검은색 칸 을 덮 었 다.
우 리 는 몇 칸 을 삭제 했다.
현재 도미 노 골패 의 최대 커버 수 를 요구 하고 있다.
당신 은 이미 알 아 차 렸 을 것 입 니 다.우 리 는 염색 한 후에 검 은 칸 과 흰 칸 은 하나의 2 분 의 그림 을 구성 할 수 있 습 니 다.모든 흰 칸 은 검 은 칸 과 만 연결 되 고 모든 검 은 칸 도 흰색 칸 과 만 연 결 됩 니 다.모든 검 은 칸 과 흰색 칸 번 호 를 준 후에 우 리 는 삭제 되 지 않 은 칸 마다 상하 좌우 로 가 까 운 삭제 되 지 않 은 칸 과 연결 합 니 다.이 2 분 그림 의 가장 큰 일치 수 는 우리 가 가장 많은 도미 노 를 내 려 놓 을 수 있다 는 것 이 분명 하 다.데이터 범위 가 넓 기 때문에 인접 표 로 그림 을 저장 해 야 합 니 다.
#include <cstdio>
#include <cstring>
#define MAXN 5500
struct Edges
{
int to, next;
} edges[MAXN * 8];
int Map[105][105], head[MAXN], p[MAXN], vis[MAXN], N, cnt_edge;
inline int add(int from, int to)
{
edges[++cnt_edge].next = head[from];
head[from] = cnt_edge;
edges[cnt_edge].to = to;
}
inline int trans(int i, int j, int n) //
{
return ((i - 1) * n + j + 1) / 2;
}
bool match(int i)
{
for (int e = head[i]; e; e = edges[e].next)
{
int j = edges[e].to;
if (!vis[j])
{
vis[j] = true;
if (p[j] == 0 || match(p[j]))
{
p[j] = i;
return true;
}
}
}
return false;
}
int Hungarian()
{
int cnt = 0;
for (int i = 1; i <= N; ++i)
{
memset(vis, 0, sizeof(vis));
if (match(i))
cnt++;
}
return cnt;
}
int main()
{
int n, m, x, y;
scanf("%d%d", &n, &m);
N = (n * n + 1) / 2;
memset(Map, -1, sizeof(Map));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
Map[i][j] = 0;
for (int i = 0; i < m; ++i)
{
scanf("%d%d", &x, &y);
Map[x][y] = -1;
}
for (int i = 1; i <= n; i++)
for (int j = i % 2 ? 1 : 2; j <= n; j += 2)
if (Map[i][j] == 0)
{
if (Map[i + 1][j] != -1)
add(trans(i, j, n), trans(i + 1, j, n));
if (Map[i][j + 1] != -1)
add(trans(i, j, n), trans(i, j + 1, n));
if (Map[i - 1][j] != -1)
add(trans(i, j, n), trans(i - 1, j, n));
if (Map[i][j - 1] != -1)
add(trans(i, j, n), trans(i, j - 1, n));
}
printf("%d
", Hungarian());
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Visual Studio에서 파일 폴더 구분 (포함 경로 설정)Visual Studio에서 c, cpp, h, hpp 파일을 폴더로 나누고 싶었습니까? 어쩌면 대부분의 사람들이 있다고 생각합니다. 처음에 파일이 만들어지는 장소는 프로젝트 파일 등과 같은 장소에 있기 때문에 파일...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
