boj 11376 - 열혈강호 2

이전에 풀었던 이분 매칭 - 열혈강호의 다음 응용 문제입니다.

 

해당 문제는 한 사람 당 일을 두 개까지 할 수 있다는 추가 조건이 존재합니다. 이는 좌측의 회사 사람 노드를 두 배로 늘려주면 됩니다.

 

예시

백준 11376에서 주어진 예제를 사용해보겠습니다.

5 5
2 1 2
2 1 2
2 1 2
2 4 5
0

 

위 입력을 단순하게 그래프를 그려보면 다음과 같습니다.

하지만 이 그래프는 노드 사람 1명마다 최대 1개의 일을 할 수 밖에 없습니다. 4번 사람을 예로 들어보죠. 사람 $v_{l4}$이 일 $v_{r4}$과 매칭시키면, 최대 일을 2개 할 수 있는 $v_{l4}$가 더이상 매칭을 만들 수 없게 되죠. $v_{r5}$의 일을 처리할 수 있는데도 불구하고 말이죠.

 

변형

 그래서 그래프에 약간의 변형을 가합니다. 사람을 2배로 늘리는 것이죠. 대신 각자 기존의 자신이 담당할 수 있었던 일을 그대로 담당하게 유지해야 합니다.

 

 

 생긴 것은 복잡하지만, 결국 $v_{l1}$과 $v_{l1'}$가 연결된 $v_{r} \in V_{R}$은 동일합니다. 모든 $v_l \in V_L$에 대해서 말이죠.

 

 이런 식으로 한 사람이 2개의 일을 처리할 수 있도록 만들었습니다.

 

한 사람이 N개의 일을 할 수 있다면?

  이전 포스트에서 다뤘던 것처럼, 사실 이분 매칭 문제는  네트워크 플로우 문제로 전환이 가능합니다. 이 문제도 $S$와 $V_L$ 사이의 유량을 2로 증가시킨다면 동일한 문제가 될 것입니다 ($v_l \in V_L$과 $v_r \in V_R$ 사이는 1). 하지만 다행히도 2개까지만 가능하기 때문에, 우리는 약간의 꼼수로 풀었습니다.

 

 만약 한 사람이 2개가 아니라 N개의 일을 할 수 있다는 조건이 주어지게 된다면 어떨까요? 무작정 $v_l \in V_L$을 $n$배 늘리는 방법은 조금 어려운 선택지로 보입니다. 이 때는 이분 매칭 알고리즘보다는 폴드-포커슨 or 에드몬드-카프와 같은 네트워크 플로우 알고리즘을 사용하는 것이 더 좋을 것 같네요.

 

 그리고... https://www.acmicpc.net/problem/11378 이 문제가 그렇습니다.

코드

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

11376번: 열혈강호 2

RUST

use std::io::{stdin, Read};
const PARENT_DEFAULT: usize = 2001;

fn dfs(i: usize, graph: &Vec<Vec<usize>>, mut parent: &mut [usize; 2000], mut visited: &mut [bool; 2000]) -> usize{
    for next in graph[i].iter(){
        if visited[*next] {
            continue;
        }
        visited[*next] = true;
        if parent[*next] == PARENT_DEFAULT || dfs(parent[*next], graph, parent, visited) == 1{
            parent[*next] = i;
            return 1;
        }
    }
    return 0;
}

fn main() {
    let mut input = String::new();
    stdin().read_to_string(&mut input).unwrap();
    let mut input = input.split_ascii_whitespace().flat_map(str::parse::<usize>);

    let N = input.next().unwrap();
    let M = input.next().unwrap();

    let mut graph: Vec<Vec<usize>> = vec![Vec::<usize>::new(); 2 * N];
    for _n in 0..N {
        let k = input.next().unwrap();

        for _k in 0..k{
            let a = input.next().unwrap();
            graph[_n * 2].push(a);
            graph[_n * 2 + 1].push(a);
        }
    }

    let mut parent: [usize; 2000] = [PARENT_DEFAULT; 2000];
    let mut ANS = 0;
    for i in 0..(2 * N) {
        let mut visited: [bool; 2000] = [false; 2000];
        ANS += dfs(i, &graph, &mut parent, &mut visited);
    }
    println!("{ANS}");
}