백준 3295번: 단방향 링크 네트워크 (C++)

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

3295번: 단방향 링크 네트워크

---

Level: Platinum II

Solved By: Bipartite Matching, Hopcroft Karp

 

문제의 내용을 요약하면 링을 구성하는 노드의 개수와 선형 배열의 노드의 개수 - 1을 구하라는 뜻입니다.

여기서 파악해야 할 것은 링의 구성 노드가 N 개라면 간선도 N 개라는 것, 그리고 선형 배열의 노드 개수가 N 개라면 간선은 N - 1개라는 것입니다.

 

즉, 최대 링과 선형 배열의 구성 노드 - 1은 노드를 연결했을 때, 노드 간 연결 간선을 최대 1개로 두었을 때, 얼마나 많이 연결할 수 있는가와 묻는 것이 같습니다.

 

더 간단하게 얘기하면 한 정점이 어떤 다른 정점과 쌍을 이룰 수 있는가를 묻는 문제입니다. 즉 정점별로 매칭을 시켜 최댓값을 구해야 합니다.

 

그럼 다시 정리해서 이 문제는 이분 매칭으로 풀 수 있습니다. 에드몬드 카프로 풀면 시간 초과가 나오기 때문에 홉크로프트 카프 알고리즘을 이용해 풀어주었습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
#define MAX 2002
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;

int N;
vector<int> adj[MAX];
bool visited[MAX];
int occupy[MAX];

void addLine(int a, int b){
    adj[a].push_back(b);
    adj[b].push_back(a);
}

bool dfs(int node){
    for(int i = 0; i < adj[node].size(); i++){
        int next = adj[node][i];
        
        if(visited[next]) continue;
        visited[next] = true;
        
        if(occupy[next] == -1 || dfs(occupy[next])){
            occupy[next] = node;
            return true;
        }
    }
    return false;
}

void init(){
    for(int i = 0; i < MAX; i++){
        adj[i].clear();
    }
}

int main(){
    FASTIO
    int T; cin >> T;
    while(T--){
        memset(occupy, -1, sizeof(occupy));
        int N, M; cin >> N >> M;
        
        for(int i = 0; i < M; i++){
            int v, u; cin >> v >> u;
            addLine(v * 2, u * 2 + 1);
        }
        
        int res = 0;
        for(int i = 0; i <= 2 * (N - 1); i += 2){
            memset(visited, false, sizeof(visited));
            if(dfs(i)) res++;
        }
        cout << res << '\n';
        if(!T) break; // 마지막 init 안 하기
        init();
    }
}