[C++] 3295번 단방향 링크 네트워크 - 이분 매칭

3295번 단방향 링크 네트워크

 

1. 문제

• 상호 접속 네트워크가 주어졌을 때 링 또는 선형 배열로 분리하여 가치의 최댓값을 구하시오. k의 노드로 이루어진 선형 배열은 k-1원, 링은 k원이다.

<입력>

• -1-   테스트 케이스 T
• -1-   노드의 수 \(n(0 \leq n \leq 1,000)\), 단방향 링크의 수 \(m(0 \leq m \leq 30,000)\)
• -m-   단방향 링크 u, v

<출력>

• -T-   분리된 상호 접속 네트워크의 가치의 최댓값

2. 재정의

• X

3. 해결 방법

• 위 문제는 다시 말해 노드가 순방향으로 연결되면서도 최대한 많이 연결되도록 자르는 문제이다. (선형 배열은 k-1개, 링은 k개 연결되어 있다.) 즉, 한 노드에서 다른 노드로 한 번만, 그리고 다른 노드에서 한 노드로 한 번만 연결되므로 이는 이분 매칭으로 최대한으로 연결했을 때 그 연결 개수를 구할 수 있다.

4. 실수한 점, 개선할 점

• X

 

<코드>

 

#include <iostream>
#include <string.h>
#include <vector>

using namespace std;

// 최대 노드 개수
const int MAX_VTX = 1001;

// <문제>
// 테스트 케이스 개수 T
int T;
// 노드의 수 N, 단방향 링크의 수 M
int N, M;
// 단방향 그래프
vector<int> vtx[MAX_VTX];

// <이분 탐색>
// 노드가 점유하고 있는 정점
int Occupy[MAX_VTX];
// 차지 여부
bool done[MAX_VTX];
// 최대 유량
int total_flow;

void input() {
    // 초기화
    total_flow = 0;
    for(int i=0; i<MAX_VTX; i++)
        vtx[i].clear();
    memset(Occupy, -1, sizeof Occupy);
    
    cin >> N >> M;
    // 그래프 생성
    for(int i=0; i<M; i++) {
        int u, v;
        cin >> u >> v;
        vtx[u].push_back(v);
    }
}

// 이분 탐색
bool dfs(int Node) {
    for(auto next : vtx[Node]) {
        if(done[next])
            continue;
        done[next] = true;
        
        if(Occupy[next] == -1 || dfs(Occupy[next])) {
            Occupy[next] = Node;
            return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> T;
    
    while(T--) {
        input();
        
        for(int i=0; i<N; i++) {
            memset(done, false, sizeof done);
            if(dfs(i))
                total_flow++;
        }
        
        cout << total_flow << '\n';
    }
    
    return 0;
}

 

 

<문제 바로가기>

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

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

 

<이분 매칭>

https://yjg-lab.tistory.com/209

[알고리즘] 이분 매칭 알고리즘 (Bipartite Matching)

 

※ 궁금한 것 질문 남겨주시면 답변드리겠습니다. 좋아요 눌러주시고 편하게 질문해 주세요.