백준 14286번: 간선 끊어가기 2 (C++)

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

14286번: 간선 끊어가기 2

---

Solved By: MFMC

 

MFMC(Max Flow Min Cut)에 대해 시작하기 좋은 문제였습니다. Max Flow와 Min Cut의 비용이 동치인 것을 알고 Max Flow를 구현하여 풀 수 있습니다.

#include <iostream>
#include <vector>
#include <queue>
#define MAX 501
#define INF 1e9
using namespace std;

vector<int> adj[MAX];
int c[MAX][MAX], f[MAX][MAX];
int n, m;

int edmondsKarp(int source, int sink){
    int result = 0;
    while(true){
        int parent[MAX];
        fill(parent, parent + MAX, -1);
        queue<int> q;
        q.push(source);
        
        while(!q.empty()){
            int now = q.front();
            q.pop();
            
            for(int i = 0; i < adj[now].size(); i++){
                int next = adj[now][i];
                
                if(c[now][next] - f[now][next] > 0 && parent[next] == -1){
                    parent[next] = now;
                    q.push(next);
                }
            }
        }
        
        if(parent[sink] == -1) break;
        
        int temp = INF;
        
        for(int i = sink; i != source; i = parent[i]){
            temp = min(temp, c[parent[i]][i] - f[parent[i]][i]);
        }
        
        for(int i = sink; i != source; i = parent[i]){
            f[parent[i]][i] += temp;
            f[i][parent[i]] -= temp;
        }
        
        result += temp;
    }
    return result;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b, w; cin >> a >> b >> w;
        adj[a].push_back(b);
        adj[b].push_back(a);
        c[a][b] = w;
        c[b][a] = w;
    }
    
    int s, t; cin >> s >> t;
    cout << edmondsKarp(s, t);
    return 0;
}