[백준/BOJ C++] 5651번 : 완전 중요한 간선 (최대 유량 알고리즘)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 5651번 : '완전 중요한 간선' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Platinum I에 해당하며, 문제를 풀이하기 위해 최대 유량(Network Flow) 알고리즘에 대한 이해가 필요합니다.

 

 

5651번 : 완전 중요한 간선

5651번: 완전 중요한 간선

 

문제 자체는 간단한데, 주어진 유량 그래프에 대해 최대 유량에 기여하는 간선의 수를 구하는 문제입니다.

최대 유량 알고리즘을 이용하여 해결해야 함은 쉽게 알 수 있지만, 알고리즘을 어떻게 활용할 것인지 고민해보아야 합니다.

 

 

#include <bits/stdc++.h>
#define MAX 305
#define INF 1e9
using namespace std;

vector<int> Line[MAX];
vector<pair<int, int>> LineInfo;
int Capacity[MAX][MAX], Flow[MAX][MAX];

void AddLine(int From, int To, int Amount) {
    Line[From].push_back(To), Line[To].push_back(From);
    Capacity[From][To] += Amount;
    LineInfo.push_back({From, To});
}

void MaxFlow(int Sour, int Sink) {
    while(true) {
        int Parent[MAX]; fill(Parent, Parent+MAX, -1);
        queue<int> Queue; Queue.push(Sour);

        while(!Queue.empty() && Parent[Sink] == -1) {
            int Curr = Queue.front(); Queue.pop();
            for(int i=0; i<Line[Curr].size(); i++) {
                int Next = Line[Curr][i];
                if(Capacity[Curr][Next] - Flow[Curr][Next] > 0 && Parent[Next] == -1) {
                    Queue.push(Next);
                    Parent[Next] = Curr;
                }
            }
        }
        if(Parent[Sink] == -1) break;

        int Amount = INF;
        for(int i=Sink; i!=Sour; i=Parent[i])
            Amount = min(Amount, Capacity[Parent[i]][i] - Flow[Parent[i]][i]);
        for(int i=Sink; i!=Sour; i=Parent[i]) {
            Flow[Parent[i]][i] += Amount;
            Flow[i][Parent[i]] -= Amount;
        }
    }
}

bool CheckEdge(int Sour, int Sink) {
    int Parent[MAX]; fill(Parent, Parent+MAX, -1);
    queue<int> Queue; Queue.push(Sour);

    while(!Queue.empty() && Parent[Sink] == -1) {
        int Curr = Queue.front(); Queue.pop();
        for(int i=0; i<Line[Curr].size(); i++) {
            int Next = Line[Curr][i];
            if(Capacity[Curr][Next] - Flow[Curr][Next] > 0 && Parent[Next] == -1) {
                Queue.push(Next);
                Parent[Next] = Curr;
            }
        }
    }
    if(Parent[Sink] == -1) return true;
    else return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int T;
    cin >> T;
    while(T--) {
        fill(&Capacity[0][0], &Capacity[MAX-1][MAX], 0);
        fill(&Flow[0][0], &Flow[MAX-1][MAX], 0);
        for(int i=0; i<MAX; i++) Line[i].clear();
        LineInfo.clear();

        int N, M;
        cin >> N >> M;
        int Sour = 1, Sink = N;
        for(int i=0; i<M; i++) {
            int f, t, b;
            cin >> f >> t >> b;
            AddLine(f, t, b);
        }
        MaxFlow(Sour, Sink);

        int Ans = 0;
        for(int i=0; i<LineInfo.size(); i++)
            if(CheckEdge(LineInfo[i].first, LineInfo[i].second)) Ans++;
        cout << Ans << "\n";
    }
}

 

먼저 최대 유량 알고리즘을 이용하여 

간선의 시작점과 끝점을 입력받는 pair vector를 추가로 하나 선언한 다음, 각각의 간선에 대해서 유량을 흘려서 Sink 노드까지 도달이 가능한지를 확인합니다.

만약 해당 간선이 문제에서 정의한 '완전 중요한 간선'에 해당한다면, 그 간선은 이미 최대치로 유량이 흐르고 있기 때문에 유량이 Sink 노드까지 도달할 수 없습니다.

이를 이용하여 모든 간선에 대해 검사를 반복해주면 주어진 시간 내에 해결이 가능합니다.

 

 

 

풀이를 제출해보면 위와 같은 시간에 문제를 해결할 수 있습니다.

다만 조건문을 추가해서 빠르게 continue 또는 break이 되도록 코드를 짜주면 50ms대 시간에도 해결이 가능합니다.