BOJ 11409 열혈강호 6 (MCMF 알고리즘 타당성)

 

문제 링크 : https://www.acmicpc.net/problem/11409

11409번: 열혈강호 6

 

Min-Cost Max-Flow 의 전형적인 문제이니 문제보다 알고리즘의 정당성에 초점을 맞추어 보자.

먼저 코드를 둘러본다.

 

#include<bits/stdc++.h>

using namespace std;

struct MCMF{
    struct edge{
        int to, cst, cap, rev;
    };
    
    int sz, Src, Ter;
    vector<vector<edge>> adj;
    vector<int> cst, prv, rIdx;
    
    MCMF(int sz, int S, int T) : sz{sz}, Src{S}, Ter{T} {
        adj=vector<vector<edge>>(sz);
    }
    
    bool spfa(){
        cst=vector<int>(sz, INT_MAX);
        prv=vector<int>(sz, -1), rIdx=vector<int>(sz, -1);
        
        vector<bool> inQ(sz, false);
        
        cst[Src]=0;
        inQ[Src]=true;
        queue<int> q;
        q.push(Src);
        
        while(!q.empty()){
            int cur=q.front();
            q.pop();
            inQ[cur]=false; 
            
            for(int i=0;i<adj[cur].size();i++){
                edge te=adj[cur][i];
                int nxt=te.to;
                if(cst[nxt]>cst[cur]+te.cst and te.cap>0){
                    cst[nxt]=cst[cur]+te.cst;
                    prv[nxt]=cur;
                    rIdx[nxt]=i;
                    
                    if(!inQ[nxt]) {
                        inQ[nxt]=true;
                        q.push(nxt);
                    }
                }
            }
        }
        return prv[Ter]!=-1;
    }
    
    void solve(){
        int tFlow=0, tCost=0;
        while(spfa()){
            int flow=INT_MAX, cost=0;
            for(int i=Ter;i!=Src;i=prv[i]){
                int p=prv[i], r=rIdx[i];
                edge te=adj[p][r];
                flow=min(flow, te.cap);
                cost+=te.cst;
            }
            
            tFlow+=flow, tCost+=flow*cost;
            
            for(int i=Ter;i!=Src;i=prv[i]){
                int p=prv[i], r=rIdx[i];
                adj[p][r].cap-=flow;
                adj[i][adj[p][r].rev].cap+=flow;
            }
        }
        
        printf("%d\n", tFlow);
        printf("%d\n", -tCost);
    }
    
    void link(int u, int v, int cst, int cap){
        adj[u].push_back({v, cst, cap, (int)adj[v].size()});
        adj[v].push_back({u, -cst, 0, (int)adj[u].size()-1});
    }
};

int main(){
    int n,m; scanf("%d%d",&n,&m);
    MCMF mcmf(n+m+2, 0, n+m+1);
    
    for(int i=1;i<=n;i++){
        mcmf.link(0, i, 0, 1);
        
        int k; scanf("%d",&k);
        for(int j=0;j<k;j++){
            int u, c; scanf("%d%d",&u,&c);
            mcmf.link(i, n+u, -c, 1);
        }
    }
    
    for(int i=1;i<=m;i++) mcmf.link(n+i, n+m+1, 0, 1);
    
    mcmf.solve();
}

 

어떤 알고리즘을 사용하는지에 따라 정당성을 설명하는 방식도 달라지기에 흔히 보이는 코드를 사용했다.

두 가지 전제를 만족한다는 가정하에 이야기를 진행한다.

 

(1) 최초에 negative cycle 이 없다.

최초 모델링에서 어떤 싸이클을 따라 돌아왔을 때, 비용이 음수가 되는 경우가 없다는 것인데...

사실 현실 문제를 모델링하면 negative cycle 이 존재하는 경우는 의외로 많다.

이 경우에는 간선의 용량에 따라 해결 가능 여부가 달라진다. 

하지만 번거로워질 것이니 여기서는 최초에는 negative cycle은 없는 대부분의 ps 문제의 가정 수용해서 논의한다.

 

(2) 간선의 용량은 모두 정수로 국한한다.

 

 

위의 코드가 최소비용(Min-Cost) 이전에 최대 유량(Max-Flow)이 확보되는지부터 생각해보자.

1. Max-Flow 를 만족하는가?

그렇다! 최대유량문제를 해결하는 방법을 떠올려보자.

 

최대유량을 찾는 방법은 간단하다.

aumenting path 를 찾아 유량을 한껏 흘려보낸 다음에 residual network 를 만드는 것을 반복하면 된다.

 

residual network 를 도입하는 것은, 이미 이루어진 선택의 일부 혹은 전체를 되돌릴 수 있게 하기 위함이다.

앞선 경로 선택이 이후 과정에서 도착점까지 가는 경로를 막아 버리는 것을 방지한다.

 

이로 인해 효율성을 고려하지 않으면

어떤 방법로 aumenting path 를 찾더라도(너비우선, 깊이우선, 뭐든 간에) 최대유량에 도달하는 것이 보장된다.

 

간선의 용량이 정수라고 한 (2)의 전제로 인해 흘려보낸 용량은 최소 1 이상 정수로 증가하므로 한계에 도달해야만 한다.

위의 코드는 최소 비용 경로를 spfa 함수를 통해 greedy 하게 찾지만,

residual network 를 만들면서 진행하는 한 aumenting path 를 찾는 것을 방해할 수 없다.

 

2 .  과정의 일부를 돌이키는데 어떻게 Min-Cost 가 보장되는가?

1 의 설명에서 최대 유량을 확보하는 과정에서 경로 일부 혹은 전체를 취소할 수 있음을 생각해보면 정당한 질문이다.

기껏 최소 비용 augmenting path 를 찾아 놓더라도,

다음 단계에서 경로 찾기에 경로 일부를 되돌릴 수 있기 때문에 최종적으로 최소비용이 되는지 확인이 필요하다.

 

주어진 유량이 흐르는 상황에서 최소 비용 유량은 negative cycle 이 없음과 동치인 것은 당연하다.

그렇다면 가정 (1)에서 최초에는 negative cycle이 없다고 했으므로,

매 단계의 residual network 에도 negative cycle 이 생기지 않음을 확인하면 충분하다.

 

결론을 부정하여 과정에서 residual network 에 최초로 negative cycle 이 생기는 순간을 가정하자.

없던 것이 생겼으므로 최초로 생성된 negative cycle 은 직전의 augmenting path 의 역간선들을 이용해야만 한다.

위 그림에서 마지막 augmenting path 가 직선처럼 보이는 Src-> A -> B ->Ter 였을 때,

새로 생긴 음수 싸이클은 화살표를 따르는 (경로 p -> B -> A) 라 하자.

 

여기서 모순을 찾을 수 있다. 음수 싸이클이라 했으니

Cost(경로 p) + Cost(B -> A) < 0

 

가 성립한다. Cost(B->A)=-Cost(A->B) 이므로

Cost(경로 p) - Cost(A -> B) < 0 이고 Cost(경로 p) < Cost(A -> B) 

 

가 성립할 것이다.  그럼 애초에 A -> B 대신 경로 p를 선택하는 비용이 더 싸다는 것이므로

Src-> A -> B ->Ter 

가 최소비용 augmenting path 가 아니었다는 뜻이 되기 때문이다.

 

모순이 야기되었으니 음수값 싸이클이 생길 수 없음을 알았다. 

결국 위의 코드는 최대 유량과 최소 비용을 모두 만족함을 알 수 있다.