[1867번] 돌멩이 제거

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 최소 버텍스 커버

2. 네트워크 플로우

3. 이분 매칭 :: http://www.crocus.co.kr/499

최소 버텍스 커버의 의미는 다음과 같다.

정점 집합 S가 있을 때, 모든 간선은 양 끝점중 적어도 하나가 S에 포함되어야 한다.

이 과정을 이용하기 위해 최소 버텍스 커버에 대해 조금 더 자세히 알아야 한다.

최소 버텍스 커버 문제임을 안다면 이 문제를 이분 매칭으로 풀 수 있다. (König's Theorem에 의해)

자세히 알기위해서는 저 정리를 제대로 봐야하지만, 문제를 풀기위해 결론적인 내용만으로 시작해보자.

그렇다면 이문제는 이제 이분 매칭으로 접근해야하는데 어떻게 이분 매칭을 생각하냐면

행과 열을 기준으로 이분 매칭을 생각해본다.

예제 입력에서 다음과 같이 주어지면 그림으로 다음과 같이 행렬로 표현할 수 있다.

위의 과정처럼 이제 이분 매칭을 하게되면 1-1과 2-2가 잡히게 될 것이다.

이때 푸른색 동그라미를 기준으로 보면

1행을 잡았을 경우 1열과 3열로 달리게 된다. 즉 1행 1열-> 1행 3열로 달린다.

2열을 잡았을 경우 2행과 3행으로 달리게 된다. 즉 2열 1행->2열 3행로 달린다.

(이분매칭으로는 사실상 정확히 몇개의 최소 버텍스 커버가 필요한지의 개수만 알려준다.)

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <vector>
#include <memory.h>
 
#define MAX_N 501
using namespace std;
 
int n, k;
int aMatch[MAX_N];
int bMatch[MAX_N];
vector<int> adj[MAX_N];
 
int visit[MAX_N];
int visitCnt;
 
bool dfs(int a)
{
    if (visit[a] == visitCnt)
        return false;
 
    visit[a] = visitCnt;
 
    for (int i = 0; i < adj[a].size(); i++)
    {
        int b = adj[a][i];
 
        if (bMatch[b] == -1 || dfs(bMatch[b]))
        {
            bMatch[b] = a;
            aMatch[a] = b;
 
            return true;
        }
        
    }
    return false;
}
 
int bipartiteMatch()
{
    memset(aMatch, -1, sizeof(aMatch));
    memset(bMatch, -1, sizeof(bMatch));
 
    int ans = 0;
 
    for (int start = 1; start <= n; start++)
    {
        visitCnt++;
        ans += dfs(start);
    }
 
    return ans;
}
int main()
{
    scanf("%d %d", &n, &k);
 
    for (int i = 0; i < k; i++)
    {
        int from, to;
        scanf("%d %d", &from, &to);
 
        adj[from].push_back(to);
    }
 
    printf("%d", bipartiteMatch());
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>