[C++] 14286번 간선 끊어가기 2 - 최대 유량, 최대 유량 최소 컷 정리

1. 문제

• 정점 n개, 간선 m개로 이루어진 가중치가 있는 무방향 그래프가 주어진다. 특정 정점 s, t가 비연결되도록 간선을 제거하는데, 제거한 간선의 가중치의 합의 최솟값을 구하시오.

<입력>

• -1- 정점의 개수 n, 간선의 수 m이 주어짐 \((2 \leq n \leq 500, 1 \leq m \leq 10,000)\)
• m줄 a와 b사이 가중치 c \((1 \leq a, b \leq n, 1 \leq c \leq 100, a \neq b)\)
• -m+2- 두 정점 s, t \((1 \leq s, t \leq n, s \neq t)\)

<출력>

• 제거한 간선의 가중치 합의 최솟값 출력

2. 재정의

• 최소컷을 구하시오.

3. 해결 방법

• 최대 유량 최소 컷 정리에 따라 최소컷은 최대 유량과 같다. 따라서 최대 유량 알고리즘을 이용해 최소컷을 구할 수 있다.

4. 실수한 점, 개선할 점

• 없음

 

<코드>

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

using namespace std;

const int INF = 987654321;
const int MAX_N = 501;

//정점의 개수 n, 간선의 수 m
int n, m;
//정점 s, t
int s, t;
//무방향 그래프
vector<int> Edge[MAX_N];
//용량, 유량, 최대유량
int capacity[MAX_N][MAX_N], flow[MAX_N][MAX_N], total_flow;
//최대 유량 알고리즘용 부모
int parent[MAX_N];

void input() {
    cin >> n >> m;
    
    for(int i=0; i<m; i++) {
        int a, b, c;
        
        cin >> a >> b >> c;
        
        Edge[a].push_back(b);
        Edge[b].push_back(a);
        
        //최대 용량은 간선의 가중치이다.
        capacity[a][b] = capacity[b][a] = c;
    }
    
    cin >> s >> t;
}

void MaximumFlow() {
    while(1) {
        memset(parent, -1, sizeof parent);
        
        //bfs
        queue<int> q;
        q.push(s);
        
        while(!q.empty() && parent[t] == -1) {
            int here = q.front(); q.pop();
            
            for(auto Next : Edge[here]) {
                if(capacity[here][Next] - flow[here][Next] > 0 && parent[Next] == -1) {
                    q.push(Next);
                    parent[Next] = here;
                }
            }
        }
        
        //s에서 t까지 갈 때 더 이상의 증가경로는 없다.
        if(parent[t] == -1)
            break;
        
        int amount = INF;
        for(int p = t; p!=s; p = parent[p])
            amount = min(capacity[parent[p]][p] - flow[parent[p]][p], amount);
        
        for(int p = t; p!=s; p = parent[p]) {
            flow[parent[p]][p] += amount;
            flow[p][parent[p]] -= amount;
        }
        
        total_flow += amount;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    //최대 유량 알고리즘
    MaximumFlow();
    
    cout << total_flow;
    
    return 0;
}

 

<최대 유량 최소 컷 정리 1>

https://restudycafe.tistory.com/430

[백준/BOJ C++] 최대 유량 최소 컷 정리 (Max-Flow Min-Cut Algorithm, MFMC)

 

<최대 유량 최소 컷 정리 2>

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=jqkt15&logNo=222063980106 

[알고리즘] Max-Flow Min-Cut Theorem (최대 유량 최소컷 정리)

 

 

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