백준 5651번: 완전 중요한 간선 (C++)

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

5651번: 완전 중요한 간선

---

Solved By: Max Flow

 

테스트 케이스를 보면서 다음 생각을 할 수 있었습니다.

 

1, 2번째 TC

Capacity와 Flow가 같은(유량이 Full인) Edge에 Capacity를 1이라도 줄이면 해당 Edge의 Flow는 줄어든다.

 

3번째 TC

어느 한 Edge에서 Capacity를 하나 줄였지만 다른 Residual Capacity가 있는 Edge에서 Flow가 생겨 Max Flow가 변하지 않는 Case도 존재하지 않을까?

 

3번째 TC를 보며 든 가설에 의해 저격형 코드를 짜봤습니다.

// Test Code

#include <iostream>
#include <vector>
#include <queue>
#define MAX 301
#define INF 1e9
#define pii pair<int, int>
using namespace std;

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

int edmondsKarp(int source, int sink){
    int result = 0;
    while(true){
        vector<int> parent(MAX, -1);
        vector<int> visited(MAX, -1);
        queue<int> q;
        
        q.push(source);
        visited[source] = true;
        
        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
                    && visited[next] == -1){
                    q.push(next);
                    parent[next] = now;
                    visited[next] = 1;
                    
                    if(next == sink) break;
                }
            }
            
            if(parent[sink] != -1) break;
        }
        
        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;
    
    vector<pii> edges;
    for(int i = 0; i < m; i++){
        int v, u, w; cin >> v >> u >> w;
        // 데이터 저격 조건문
        if(v == 3 && u == 4){
            w = 3;
        }
        edges.push_back({v, u});
        adj[v].push_back(u);
        adj[u].push_back(v);
        c[v][u] = w;
    }
    
    cout << edmondsKarp(1, n) << '\n';
    
    for(auto& [i, j] : edges){
        cout << i << ' ' << j << '\n';
        cout << c[i][j] << ' ' << f[i][j] << '\n';
        cout << "==========" << '\n';
    }
    return 0;
}

코드를 통해 원하는 Edge의 Capacity를 1씩 줄여보면서 가설이 참임을 증명할 수 있었습니다.

 

즉, 문제의 포인트를 정리해본다면 '어떤 Edge가 중요하지 않다면 그 Edge를 거치지 않더라도 다른 경로를 통해 유량을 흘릴 수 있어야 합니다.'

 

이 점에서 이 문제는 백준 1210번: 마피아 문제와 흡사합니다. (https://draw-code-boy.tistory.com/363)

1210번 문제에서도 BFS를 통해 유량을 흘려보낼 수 있다면 node를 방문할 수 있다고 짜두었습니다. 이 테크닉을 사용하여 문제를 풀 수 있었습니다.

 

+ Capacity 값을 입력받을 때, 같은 Edge에 입력이 들어오면 새로 할당을 하여 문제를 틀렸었는데 기존에 입력된 Capacity가 있을 수 있으므로 더해주어야 맞습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
#define MAX 301
#define INF 1e9
#define pii pair<int, int>
using namespace std;

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

int edmondsKarp(int source, int sink){
    int result = 0;
    while(true){
        vector<int> 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(parent[next] == -1 &&
                    c[now][next] - f[now][next] > 0){
                    q.push(next);
                    parent[next] = now;
                    
                    if(next == sink) break;
                }
            }
            
            if(parent[sink] != -1) break;
        }
        
        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 bfs(vector<pii>& edges){
    int result = 0;
    for(auto edge : edges){
        int s = edge.first, e = edge.second;
        if(c[s][e] != f[s][e]) continue;
        
        int par[MAX];
        memset(par, -1, sizeof(par));
        queue<int> q; q.push(s);
        while(!q.empty()){
            int now = q.front(); q.pop();
            for(int i = 0; i < adj[now].size(); i++){
                int next = adj[now][i];
                if(par[next] == -1 && c[now][next] - f[now][next] > 0){
                    par[next] = now; q.push(next);
                }
            }
        }
        
        if(par[e] == -1) result++;
    }
    return result;
}

int main(){
    cin >> T;
    while(T--){
        cin >> n >> m;
        
        // init
        for(int i = 0; i < MAX; i++) adj[i].clear();
        memset(f, 0, sizeof(f));
        memset(c, 0, sizeof(c));
        
        vector<pii> getEdges;
        
        for(int i = 0; i < m; i++){
            int v, u, w; cin >> v >> u >> w;
            getEdges.push_back({v, u});
            adj[v].push_back(u);
            adj[u].push_back(v);
            c[v][u] += w;
        }
        
        edmondsKarp(1, n);
        int ans = bfs(getEdges);
        cout << ans << '\n';
    }
    return 0;
}