[C++] 11377번 열혈강호 3 - 최대 유량, 이분 매칭

1. 문제

• 강호네 회사는 직원이 N명, 해야 할 일이 M개가 있다. 직원은 1~N번, 일은 1~M번으로 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 직원은 1명이다. 단 N명 중에 K명은 일을 2개 할 수 있다. 각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오.

<문제>

• -1-   직원의 수 N, 일의 개수 M, 일을 2개 할 수 있는 직원의 수 K \((1 \leq N, M \leq 1000, 1 \leq K \leq N)\)
• -N개-   i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다.

<출력>

• 강호네 회사에서 할 수 있는 일의 개수를 출력하라.

2. 재정의

• N명 중 K명은 2개, 그 외는 1개의 각자가 할 수 있는 일을 할 수 있을 때 할 수 있는 일의 최대 개수를 구하시오.

3. 해결 방법

그래프 구성

4. 실수한 점, 개선할 점

• Edge 구조체를 만들어서 했다가 시간 초과가 났다. 이는 그냥 메모리를 더 사용함으로써 시간을 줄일 수 있다.
• 최대 2번인 경우 그냥 dfs를 2번 돌려주면 된다. 이 경우 소요 시간을 효과적으로 줄일 수 있다. (이렇게 짠 코드의 링크는 아래에 있다.)

 

 

<코드>

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

using namespace std;

const int INF = 987654321;
const int MAX_V = 2004;
const int WORK = 1000;

//직원의 수 N, 일의 개수 M, 일을 2개 할 수 있는 직원의 수 K
int N, M, K;
int S, E, X;
//최대 유량 알고리즘을 적용할 그래프
vector<int> adj[MAX_V];
//용량, 유량
int capacity[MAX_V][MAX_V], flow[MAX_V][MAX_V];

//간선 생성하기
void makeEdge(int u, int v, int c) {
    capacity[u][v] = c;
    
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void input() {
    S = 0, E = 2003, X = 2002;
    
    cin >> N >> M >> K;
    
    //방향 그래프 만들기
    makeEdge(0, X, K);
    for(int i=1; i<=N; i++) {
        makeEdge(0, i, 1);
        makeEdge(X, i, 1);
    }
    for(int i=WORK+1; i<=WORK+M; i++)
        makeEdge(i, E, 1);
    for(int i=1; i<=N; i++) {
        int worknum, work;
        cin >> worknum;
        for(int j=0; j<worknum; j++) {
            cin >> work;
            makeEdge(i, WORK+work, 1);
        }
    }
}

//최대 유량 알고리즘
int MaxFlow() {
    int total_flow = 0;
    while(1) {
        //부모 노드와, 길
        int parent[MAX_V];
        
        queue<int> q;
        
        //배열 초기화
        memset(parent, -1, sizeof parent);
        
        //dfs
        q.push(S);
        
        while(!q.empty() && parent[E] == -1) {
            int here = q.front(); q.pop();
            
            for(auto there : adj[here]) {
                //탐색할 곳
                if(capacity[here][there] - flow[here][there] > 0 && parent[there] == -1) {
                    parent[there] = here;
                    q.push(there);
                }
            }
        }
        //더 이상의 증가 경로가 없으므로 종료
        if(parent[E] == -1)
            break;
        
        //탐색한 경로로 흘려줄 수 있는 최대 유량
        int amount = INF;
        for(int p = E; p!=S; p = parent[p])
            amount = min(amount, capacity[parent[p]][p] - flow[parent[p]][p]);
        for(int p = E; p!=S; p = parent[p]) {
            flow[parent[p]][p] += amount;
            flow[p][parent[p]] -= amount;
        }
        
        total_flow += amount;
    }
    
    return total_flow;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    cout << MaxFlow();
    
    return 0;
}

 

<dfs로 푼 코드>

https://j3sung.tistory.com/413

[C++] 백준 11377번 열혈강호 3

 

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.