[백준 7616번] [네트워크 플로우 / 정점 분할] 교실로 가는 길

이 문제에서 가장 중요한 지점은 경로도 겹치지 말아야하지만 노드도 겹치면 안된다는 점이다.

 

경로가 겹치지 않는 것은 최대유량으로 충분히 처리할 수 있다. 그런데 노드가 겹치지 말아야한다는 것은 일종의 노드에 capacity를 주는 느낌으로 이해할 수 있다.

 

이를 해결하기 위해서는 정점을 in과 out을 구분하는 "정점 분할"을 활용하면 된다.

서로 다른 노드끼리 연결하는 경우에는 반드시 out -> in으로만 가능하고

내부 정점에서는 in -> out로만 이동하게 하고 in -> out에 capacity를 1을 줌으로써 해결할 수 있다.

 

대략적으로 이런방식으로 처리를 해주면 된다.

그러면 한 노드 안에서도 capacity가 생성되어 1번만 방문하게끔 유도할 수 있다.

 

다만, 유의해야할 점은 flow를 줘가면서 경로를 추적하면 안된다.

왜냐하면 역방향 간선에 의해 경로가 수정될 수 있기 때문이다.

즉, 이러한 특성때문에 augmenting path에서 방문한 노드라고 해서 끊어버리면 안된다.(해당 내용은 이미 데이터 추가 요청한 상황이다.)

따라서 max_flow가 K이상인지를 확인해주고, sink를 기준으로 역으로 추적해나가면 된다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

const int MAX_N = 10002;

using namespace std;
int K, N;
struct edge{
    int from, to;
    int capacity, flow;
    edge* reverse_edge;
    edge(int u, int v, int c) : from(u), to(v), capacity(c), flow(0)
    {}

    int residual(){
        return capacity - flow;
    }

    void add_flow(int amount){
        flow += amount;
        reverse_edge -> flow -= amount;
    }
};

void add_edge(int u, int v, int c, vector<edge*> *adj, bool dir = true){
    edge* e1 = new edge(u, v, c);
    edge* e2 = new edge(v, u, dir ? 0 : c);
    e1 -> reverse_edge = e2;
    e2 -> reverse_edge = e1;
    adj[u].push_back(e1);
    adj[v].push_back(e2);
    return;
}

vector<edge*> adj[MAX_N];

int networkFlow(int source, int sink){
    int max_flow = 0;
    while(true){
        vector<edge*> parent(MAX_N, nullptr);
        queue<int> q;
        q.push(source);
        while(!q.empty() && parent[sink] == nullptr){
            int here = q.front(); q.pop();
            for(int p = 0; p < adj[here].size(); p++){
                if(adj[here][p]->residual() > 0 && parent[adj[here][p] ->to] == nullptr){
                    q.push(adj[here][p] -> to);
                    parent[adj[here][p] -> to] = adj[here][p];
                }
            }
        }
        if(parent[sink] == nullptr) break;

        for(int p = sink; p != source; p = parent[p] -> from){
            if(p != 1 && p != 3) parent[p] -> add_flow(1);
        }
        max_flow++;
    }
    return max_flow;
}

int print_count = 0;
vector<int> print_store[100];

void print(int check_num){
    if(print_count == K) return; // Early exit

    if(check_num == 0){
        print_store[print_count].push_back(1);
        print_count++;
        return;
    }
    else{
        if(check_num % 2 == 1) print(check_num - 1);
        else{
            for(int i = 0; i < adj[check_num].size(); i++){
                if(adj[check_num][i] ->residual() > 0 && adj[check_num][i] -> to != 3){
                    print_store[print_count].push_back((check_num + 2) / 2);
                    print(adj[check_num][i] -> to);
                }
            }
        }
    }
}
int main(void){
    int case_num = 1;
    
    while(true){
        cin >> K >> N;
        if(K == 0 && N == 0) return 0; // 종료인 상황

        for(int i = 1; i <= N; i++){
            add_edge(i * 2 - 2, i * 2 - 1, 1, adj);
        }

        for(int i = 1; i <= N; i++){
            int path_num; char check_data;
            while(true){
                scanf("%d%c", &path_num, &check_data);
                add_edge(i * 2 - 1, path_num * 2 - 2, 1, adj);
                if(check_data == '\n') break;
            }
        }
        cout << "Case " << case_num << ":\n";
        if(networkFlow(0, 3) >= K){
            print_count = 0;
            print(3);
            for(int i = 0; i < K; i++){
                for(int j = print_store[i].size() - 1; j >= 0; j--){
                    cout << print_store[i][j] << " ";
                }
                cout << "\n";
            }
        }
        else cout << "Impossible\n";
        cout << "\n";

        // Dummy data reset
        for(int i = 0; i < MAX_N; i++){
            adj[i].clear();
        }
        for(int i = 0; i < 100; i++){
            print_store[i].clear();
        }
        case_num++;
    }
}

특히 정점분할 테크닉에 대해서 잘 정리해두도록 하자.