백준 21010번: Slow Down (C++)

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

21010번: Slow Down

---

Solved By: Dijkstra, MFMC

 

다익스트라를 돌려서 최단 경로를 구합니다. 그리고, 백준 1948번:임계 경로(https://draw-code-boy.tistory.com/337)에서 사용한 역방향 BFS 테크닉으로 경로가 몇 개인지 구하려 했습니다.

 

사용하려 했던 테크닉의 방향:

다익스트라로 최단 경로 가중치를 구하여 역방향 BFS를 통해 최단 경로를 유발하는 경로 개수를 찾아서(prev == 1이면 카운트하는 방식, 중간에 겹치는 길이 있을 수 있으므로 방문 체크 안 함) 방문 체크를 하지 않다 보니 시간 초과가 발생함.

 

하지만, 문제에서 구하고자 하는 바는 달랐습니다. 제가 구하고자 하던 방향에는 반례를 찾을 수 있었습니다.

최단 경로를 유발하는 노드들을 역방향 BFS를 통해 모아서 그래프를 그렸다고 가정합시다. 이 과정에서 1에서 N까지 갈 수 있는 경로는 총 4개입니다. 하지만, 답은 3입니다.

 

왜냐하면 문제에서 요구하는 건 1에서 출발했을 때, N까지 도착하는 이동하는 시간이 최소 1이 증가하도록 하는 총 최소 비용이니까요.

즉, 민트색으로 체크한 edge에 가중치만 1씩 더하면 해결이 됩니다.

 

그래서 생각해낸 건 역방향 BFS를 돌리면서 최단 경로를 유발하는 edge들의 capacity를 1로 주고, 1부터 N까지의 Max Flow를 구하여 MFMC를 만들어내는 것입니다.

(이번엔 각 edge들을 구하는 것이니 방문 체크를 해야겠죠.)

 

즉, 솔루션을 정리하자면

1) 다익스트라를 통해 최단 경로 값을 구한다.

2) 역방향 BFS를 통해 최단 경로를 유발하는 edge들을 구한다.

3) 해당 edge들의 capacity를 1로 부여한다.

4) Source = 1, Sink = N으로 MFMC를 구한다.

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

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

struct cmp{
    bool operator()(pii &a, pii &b){
        return a.second > b.second;
    }
};

vector<int> dijkstra(int node){
    priority_queue<pii, vector<pii>, cmp> pq;
    pq.push({node, 0});
    vector<int> dist(n + 1, INF);
    dist[node] = 0;
    
    while(!pq.empty()){
        int now = pq.top().first;
        int nowCost = pq.top().second;
        pq.pop();
        
        if(dist[now] < nowCost) continue;
        
        for(int i = 0; i < adj[now].size(); i++){
            int next = adj[now][i].first;
            int nextCost = adj[now][i].second;
            
            if(dist[now] + nextCost < dist[next]){
                dist[next] = dist[now] + nextCost;
                pq.push({next, dist[next]});
            }
        }
    }
    return dist;
}

void bfs(vector<int>& dist){
    queue<int> q; q.push(n);
    vector<bool> visited(n + 1, false);
    visited[n] = true;
    int cnt = 0;
    
    while(!q.empty()){
        int now = q.front();
        q.pop();
        
        for(int i = 0; i < adj[now].size(); i++){
            int prev = adj[now][i].first;
            int prevCost = adj[now][i].second;
            
            if(dist[now] - prevCost == dist[prev]){
                
                c[prev][now] = 1;
                if(!visited[prev]){
                    visited[prev] = true;
                    q.push(prev);
                }
            }
        }
    }
}

int edmondsKarp(int source, int sink){
    int maxFlow = 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].first;
                
                if(c[now][next] - f[now][next] > 0 && parent[next] == -1){
                    //cout << now << ' ' << next << '\n';
                    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;
        }
        
        //cout << temp << '\n';
        maxFlow += temp;
    }
    
    return maxFlow;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b, w; cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    
    auto dist = dijkstra(1);
    bfs(dist);
    cout << edmondsKarp(1, n);
    
    return 0;
}