플로우를 이용한 그리디 알고리즘의 증명 (1)

그리디 알고리즘은 그 발상에 따라 난이도가 천차만별이기로 유명하다. 회의실 배정과 같이 기초적인 그리디 문제는 실버에서 시작하는 반면, Scenery 같은 문제는 루비까지 올라가기도 한다. (사실 난 Scenery의 풀이를 잘 모르기 때문에 단순 그리디가 아닐 수도 있다.) 그리디 전략을 증명할 때 사용하는 방법 중 하나가 플로우를 이용하는 것이다. 플로우는 분명 OI 범위 밖이지만, 그리디 알고리즘은 OI 범위 안이고, 플로우를 이용한 증명은 플로우 없이도 할 수 있는 경우가 많아 OI에서 심심찮게 볼 수 있었다. 난 이러한 증명 방식에 대해 잘 몰랐기 때문에 이런 문제를 만날 때마다 힘들었는데, 이제는 공부해 볼 때가 되었다고 생각해 공부를 시작해 보았다.

 

이 글은 이해하는 데 초점을 맞추었기 때문에 별로 엄밀하지 않다. 엄밀한 증명을 원하면 다른 글을 보는 것이 좋을 것이다. 참고한 글들은 다음과 같다: 1, 2, 3, 4, 5

 

글에 있는 많은 연습문제들을 추천해 주고 플로우에 대한 다양한 자료를 주신 qwerasdfzxcl님, koosaga님, jhnah917님께 감사의 말씀을 드린다.

플로우?

일단 플로우에 대한 기본적인 이야기로 시작해보자. 이 글을 쓰는 시점에서 난 플로우의 기본 중의 기본만 알고 있기 때문에 자세히 쓰고 싶어도 못 쓴다. 그렇기 때문에 이 글을 이해하는 데에 필요한 정도로만 대충 쓰고 넘어갈 생각이다.

 

가장 기본적인 형태의 Network-Flow 문제는 다음과 같이 정의된다.

• 어떤 그래프 $G$가 있고, 시작점(source node) $s$와 끝점(sink node) $e$가 존재한다.
• 시작점 $s$부터 끝점 $e$까지 간선을 타고 유량을 흘려야 하는데, 각 간선에는 최대로 흘릴 수 있는 용량(capacity) $c_i$가 정해져 있다.
• 흘릴 수 있는 최대 유량을 구해야 한다.

유량이라는 개념을 처음 접한다면 이 개념이 잘 이해되지 않을 수 있는데, 그렇다면 $s$부터 $e$까지 유량을 흘리는 것을 경로를 선택한다고 생각해도 좋다. 예컨대, $s$부터 $e$까지 향하는 경로를 최대한 많이 만들 것인데, $i$번 간선은 이 경로들에 최대 $c_i$번까지 등장할 수 있을 때, 경로를 최대한 많이 선택하는 문제로 봐도 좋다.

 

 

예를 들어, 위와 같은 그래프가 있고, 빨간색 수들이 각 간선의 용량이라고 하자. 시작점(소스 노드)는 $1$번 정점이고, 도착점(싱크 노드)는 6번 정점이다.

 

 

위 그림과 같이 보내면 총 6의 유량을 보낼 수 있다. 물론, 위 그림을 보면 아직 최대 용량만큼 유량을 보내지 않는 간선들이 있다. $1$번에서 $2$번 정점으로 가는 간선은 용량이 $7$이지만 $4$만큼의 유량만 보내고 있다. 이 경우 간선의 잔여 용량은 해당 간선에서 더 보낼 수 있는 유량으로 정의한다. 예를 들어 $1$번에서 $2$번 정점으로 가는 간선의 잔여 용량은 3이다.

 

위 그림을 보면, 유량을 더 많이 보낼 수 있다는 생각을 할 수 있다. 왜냐하면 $1$번에서 $2$번 정점으로 가는 간선의 잔여 유량이 $3$, $2$번에서 $5$번으로 가는 간선의 잔여 유량이 $2$, $5$번에서 $6$번으로 가는 간선의 잔여 유량이 $4$로, 잔여 유량이 있는 간선만으로 $s$에서 $e$까지 도달할 수 있기 때문이다. 이렇게 유량을 더 보낼 수 있는 경로를 증가 경로라고 한다. 실제로 해당 간선을 이용해 $2$의 유량을 추가로 보낼 수 있고, 이 증가 경로를 반영하고 나면 다음과 같이 된다.

 

 

유량 알고리즘을 익히다 보면, "유량을 흘린다"를 "가중치"의 면에서 생각하면 많이 유리함을 알 수 있다. 초기에 모든 간선의 가중치 $f_i=0$이다. 플로우 용어로 설명하면, $f_i$는 현재 $i$번 간선에 흘러가고 있는 유량을 뜻한다. 만약 $i$번 간선에 $c$의 유량이 더해진다면, $f_i$에 $c$가 더해진다. $i$번 간선의 용량은 $c_i$이므로, 언제나 $f_i \le c_i$를 만족해야 한다.

 

유량 알고리즘에서는 이미 존재하는 유량을 취소하기 위해 "역방향 유량"이라는 개념을 도입하기도 한다. 예를 들어, 현재 상황이 아래와 같다고 하자.

 

 

그래프를 딱 보면 우리는 최대 $20$의 유량을 보낼 수 있음을 알 수 있지만, 실제로 저 그림을 보면 $1$의 유량밖에 보내지 못하는 상태에서 증가 경로를 찾을 수 없다. 이런 경우는 어떻게 해야 할까? 해답은, $3$번 정점에서 $2$번 정점으로 가는 $-1$의 유량이 있다고 생각하는 것이다. 현재 $3$번 정점에서 $2$번 정점으로 가는 간선이 없으므로, 이 가상의 간선의 용량은 $c_i = 0$이다. 이제 $1 \rightarrow 3 \rightarrow 2 \rightarrow 4$의 경로에 있는 모든 간선에서 $f_i < c_i$를 만족하므로 이 경로는 증가 경로이고, 이 증가 경로를 반영하면 상황은 다음과 같이 변한다.

 

 

정방향 유량과 역방향 유량이 동시에 있어 헷갈리지만, 실제로 위 상황은 다음과 동치이다. (실제로 어떤 증가 경로로 유량을 흘려 줬는지가 중요한 게 아니라, $f_i$, 즉 각 간선별로 얼마의 유량을 보내고 있는지만 중요하기 때문이다.)

 

 

Network Flow 문제를 실제로 해결하는 알고리즘 중 가장 기본적인 것은 포드-풀커슨 알고리즘이다. 이 알고리즘은 증가 경로를 (어떤 식으로든) 계속 찾아서 유량에 추가하는 방식으로 최대 유량을 얻는다. 포드-풀커슨 알고리즘의 정당성은 이런 증가 경로를 찾는 것을 반복해 최대 유량을 찾을 수 있음을 시사한다. 이것은 일종의 그리디한 전략으로 볼 수 있고, 따라서 Greedy Algorithm의 정당성을 증명하는 데에도 Network Flow를 이용한 모델링이 사용될 수 있다.

접근법 1. 증가 경로를 찾는 것을 반복해 최대 유량을 보낼 수 있다.

MCMF

여기까지 이해했으면 MCMF의 개념은 그다지 어렵지 않다. MCMF는 비슷하게 최대 유량을 흘리는 문제인데, 각 간선별로 비용 $d_i$가 정해져 있어, 해당 간선으로 $f_i$만큼의 유량을 보내려면 $d_i f_i$의 비용이 든다. 최대 유량을 최소 비용으로 보내는 방법을 찾는 것이 문제이다.

 

예를 들어, 아래 상황을 보자. 빨간색 수(왼쪽에 있는 수)는 간선의 용량 $c_i$, 파란색 수 (오른쪽에 있는 수)는 비용 $d_i$를 나타낸다.

 

 

최대 유량은 $4$이다. 그런데 이 유량을 보내는 방법은 여러 가지가 있다. 다음과 같은 경우를 생각해 보자.

 

 

이렇게 $4$의 유량을 보낼 경우, 필요한 비용은 $4 \times (2+6+2) = 40$이다.

 

 

반면 위와 같이 $4$의 유량을 보낼 경우, 필요한 비용은 $2 \times (2+4+1) + 2 \times (2+6+2) = 34$이다. 이 방법이 최대 유량($4$)을 보내는 가장 적은 비용이 드는 방법이다.

 

MCMF 알고리즘은 증가 경로 중 최단 경로를 최단 거리 알고리즘을 통해 찾아 플로우에 반영하는 방식으로 진행된다. 최단 거리 알고리즘 중 벨만 포드 알고리즘(정확히는 벨만 포드 알고리즘을 더 빠르게 변형시킨 SPFA 알고리즘)을 사용하는데, 그 이유는 역방향 유량 때문이다. 역방향 유량은 이미 존재하는 유량을 취소하는 역할을 하기 때문에, 음의 비용이 든다. 그런데 다익스트라와 같은 최단 거리 알고리즘은 모든 간선 비용이 음이 아닌 정수일 때만 동작하므로, 음의 비용을 처리할 수 있는 SPFA 알고리즘을 사용하는 것이다.

 

MCMF 알고리즘이 시사해주는 그리디적인 관점은 다음과 같다: 최소 비용의 증가 경로를 찾는 것을 반복해 MCMF 문제를 해결할 수 있다.

접근법 2. 최소 비용의 증가 경로를 찾는 것을 반복해 최소 비용으로 최대 유량을 보낼 수 있다.

그리디 알고리즘 문제의 증명

이러한 플로우 지식이 그리디 문제를 해결하는 데 어떤 도움이 될 수 있을까? 가장 대표적인 것은 어떤 "최적화 문제"(보통, 문제에서 주어진 양을 최대화/최소화시키는 문제)를 해결할 때, 해당 문제의 상황을 최대 유량이나 MCMF로 모델링하는 것이다. 이 모델링이 플로우 문제를 거의 풀어보지 않았던 나에게는 매우 힘들었던 것 같다.

 

이 이후로 나오는 문제들을 푸는 대략적인 방법을 일반화해 보자면, 일단 문제 상황을 플로우로 모델링해야 한다. 문제들을 보면 이분 매칭 비슷하게 한 집합에서 다른 집합으로 흘려 주는 상황을 만드는 경우가 많은데, 이러한 구조가 문제에 명시적으로 있거나, 없다면 문제 상황을 잘 관찰해서 만들어야 한다. 이후 해당 그래프에서 어떻게 플로우를 흘릴지 설계하고, MCMF가 필요한 경우 비용까지 정해 줘야 한다.

 

이 시점에서 뭔가를 더 자세히 이야기하긴 어렵고, 문제와 직접 부딪혀보면서 생각하는 쪽이 얻는 게 더 많은 것 같다.

BOJ 1150. 백업

매우 유명한 고전 그리디 문제다. 나는 이 문제를 여러 번 풀었지만 다시 볼 때마다 풀이를 잊어버린다. 사실 이 문제를 오랜만에 다시 봤다가 풀이가 생각이 안 나서 이 글을 쓰기 시작한 것이기도 하다.

 

이 문제를 대체 어떻게 Flow로 모델링할 수 있을까? 사실 이걸 생각하는 부분이 이런 류 문제에서 가장 어려운 부분이다. 이 문제는 최소 비용을 이야기하고 있기 때문에, 아무래도 단순한 Flow 모델보다는, 먼저 그래프의 플로우 형태로 문제의 조건을 만족하는 해들이 나오도록 한정시켜 놓고, 그 비용을 MCMF 모델로 계산하는 것이 옳아 보인다. 무슨 뜻인지 모르겠다면 그냥 아래 흐름을 따라가 보자.

 

먼저, 그래프를 잘 구성해 해당 그래프에서 나올 수 있는 최대 유량이 문제의 조건을 만족하도록 $k$개의 건물 쌍을 연결하는 것과 동치가 되도록 해 보자. 우선 답이 될 수 있는 해에 대해 관찰을 해야 한다. 일단 자명하게도 최종 상태에서 연결되어 있는 회사들은 무조건 인접한 쌍뿐일 것이다. 즉, 답이 $1-2$, $4-5$ 와 같이 인접한 회사들이 연결된 형태로 나온다는 것이다. 이 사실을 관찰하고 직관적으로 모델을 만들려고 시도한다면 대략 다음과 같은 형태를 시도해볼 것이다. (빨간색은 간선의 용량이고, 아래에 나오는 모든 간선들의 방향은 왼쪽에서 오른쪽으로 가는 방향만 존재한다고 생각한다.)

 

 

위와 같은 형태로 모델링을 하면, 가운데 부분에서 쓰인 $k$개의 간선이 마치 우리의 답, 즉 어떤 건물들을 연결할 것인가를 정하고 있다고 생각할 수 있다. 위 상황에서 인접하지 않은 건물 쌍 (예를 들어 $2-4$)은 연결하는 것이 불가능해지지만, 이런 케이스는 어차피 답이 될 수 없기에 무시해도 된다. 그런데 문제는 저렇게 모델링을 하면 아래 그림과 같은 상황이 나올 수 있다는 것이다.

 

 

위와 같은 해가 만약 나온다면, 이 해는 $2-3$ 간선과 $3-4$ 간선을 동시에 사용하고 있으므로, $2$번과 $3$번 건물, $3$번과 $4$번 건물을 동시에 연결하고 있는 해가 된다. 이는 문제의 조건에 맞지 않는 해가 된다. 따라서, 모델을 조금 수정해야 한다. 이 문제에서 인접한 건물만을 묶게 되면, (건물들의 번호가 위치순으로 정렬되어 있을 때) 항상 홀수 건물과 짝수 건물만이 묶인다는 사실을 생각해 보자. 그렇다면 다음과 같은 모델링을 시도하는 것도 가능하다.

 

 

위와 같이 그래프를 모델링할 경우, 왼쪽에서 오른쪽 방향으로 흘리는 모든 유량은 확실히 인접한 건물 두 개의 쌍을 정하는 것과 동치가 된다. 예를 들어, 아래와 같은 결과가 나올 경우, $2-3$번 건물과 $4-5$번 건물을 연결하는 해와 동치라고 생각할 수 있다.

 

 

이런 방식으로 모델링할 경우 확실히 한 건물이 두 번 들어가는 해는 절대 나오지 않을 것이다. 각 건물에서 시작/끝 노드로 가는 용량이 $1$이기 때문이다. 그런데 아무래도, 조금 특이하게 생긴 해가 나올 우려가 아직 남아있는 것 같다. 예컨대, 아래와 같은 경로는 어떻게 해석해야 하는가?

 

 

앞에서 모든 간선의 방향은 왼쪽에서 오른쪽으로 가는 방향이라고 했기 때문에, 조금 억지 같아 보이기도 하지만, 증가 경로와 역방향 유량을 생각한다면 위와 같은 증가 경로도 충분히 나올 수 있다. 사실 위와 같은 경로의 존재성은 이 문제를 푸는 데 있어 매우 중요하다고 할 수 있다. 일단 이 이야기를 지금 하기에는 조금 이르니 그래프 모델링으로 되돌아가 보자. 이제 그래프의 모델 자체는 다 만들었고, MCMF 모델을 만들어서 답을 구하는 단계가 왔다. 각 간선에 어떤 비용을 주는 것이 좋을까? 자명하게도, 가운데 간선에는 해당 두 건물의 거리만큼의 비용을, 나머지 간선에는 $0$의 비용을 주면 될 것이다. 예제의 경우를 모델링해 보면 아래와 같다. (비용은 파란색이고, 비용을 명시하지 않은 간선은 모두 비용이 $0$이다.)

 

 

예제에서 $k=2$이고, 이때 MCMF의 해는 아래와 같다.

 

 

위 해의 총 비용이 $4$라는 것을 알 수 있고, 이는 예제 출력과 같다.

 

이제 MCMF 모델링을 어떻게 하는지까지는 살펴보았다. 하지만 위 모델링으로는 문제를 풀 수 없을 것이다. 플로우 알고리즘이 엄청 빠르다고는 하지만 이 정도 크기에서까지 도는 것을 기대하기는 힘들다. (사실 안 짜봐서 모른다. 될 수도 있다.) 그러나 우리는 저 MCMF 모델을 직접 이용해서 문제를 풀 것이 아니라, 저 상황에서 MCMF 알고리즘이 동작하는 과정으로부터 아이디어를 얻어 문제를 그리디 알고리즘으로 해결할 것이다.

 

위와 같은 그래프가 있다고 생각해 보자. 증가 경로로 가능한 형태는 어떤 것이 있을까? 만약 건물 $x$와 $x+1$이 모두 연결되지 않은 상태라면 이 두 건물을 연결하는 것이 가능하다. 여기에 해당하는 증가 경로는 아래 그림과 같은 형태이다.

 

 

반면, 앞에서 문제가 되었던 아래와 같은 증가 경로도 있다. 이 증가 경로가 하는 역할이 무엇인가?

 

 

이미 초록색 유량이 있었던 상태에서, 보라색 경로가 추가되었다고 생각해 보자. (보라색 경로가 $2$에서 $3$으로 갈 수 있는 이유는 초록색 경로를 상쇄하면서 생기는 역방향 유량 때문이다.) 이 보라색 경로가 하는 일은, 초록색 $2-3$ 연결을 끊고 보라색 $1-2$, $3-4$ 경로를 동시에 만드는 것이다. 지금은 그림의 크기 자체가 적기 때문에 하나의 연결을 끊는 데 그쳤으나, 일반적으로는 $c$개의 연결을 끊고 $c+1$개의 연결을 만드는 형태도 가능할 것이라고 볼 수 있다.

 

즉, 증가 경로는 항상 다음 중 하나의 형태이다.

• 아직 연결되어 있지 않은 두 점 $p$와 $p+1$을 골라, $p \leftrightarrow p+1$ 연결을 만든다.
• 만약 $p$와 $p+2k+1$이 아직 연결되어 있지 않고, $p+1 \leftrightarrow p+2$, $p+3 \leftrightarrow p+4$, $\cdots$, $p+2k-1 \leftrightarrow p+2k$가 모두 연결되어 있다면 $(k \ge 1)$, 이 연결을 모두 끊고 $p \leftrightarrow p+1$, $p+2 \leftrightarrow p+3$, $\cdots$, $p+2k \leftrightarrow p+2k+1$ 연결을 모두 만든다.

MCMF 알고리즘의 정당성(접근법 2)는 위 두 가지 종류의 행동 중 가장 싼 것을 $k$회 진행했을 때 항상 최적해를 얻음을 보장한다. (항상 $k$회인 이유는, 위 두 가지 종류의 행동은 모두 연결의 개수를 정확히 $1$씩 늘리기 때문이다.)

 

이렇게 문제를 변형하게 되면 priority_queue나 set 등의 자료구조를 적절히 활용해 문제를 풀 수 있다. 시간 복잡도는 $O(N \log N)$이다.

BOJ 29772. 병사 분배

일단 문제를 보아하니 최대 능력치를 구해야 하는데, 뭔가 최소가 아니라 최대라고 하니까 MCMF로 할 수 있는 게 맞나 싶은 생각이 든다. 또 각 병사별로 K명 이상이 필요하다는 조건도 플로우 모델링으로 가능할지 잘 모르겠다. 차라리 K명 이하였다면 용량을 K로 제한하면 되겠지만… 그렇다면 반대로 생각하는 건 어떨까?

 

가장 자명한 모델링은 $i$번 병사와 $j$번 장군에 대해, $i$번 병사와 $j$번 장군을 연결할 경우 유량을 흘리는 것이겠지만, 이러면 위에서 본 문제점들이 생긴다. 따라서, $i$번 병사와 $j$번 장군을 연결하지 않을 때 유량을 흘려 준다고 생각하자. 그럼 아래 그림과 같은 모델링이 가능하다.

 

 

위 모델링에서 가운데에 있는 간선들은 용량이 모두 $1$이다.

 

위와 같이 모델링했을 때 조건을 만족하는 배치만 나온다는 사실을 먼저 증명해 보자. $i$번 병사와 $j$번 장군을 잇는 간선에 유량이 흐르는 것은 $i$번 병사가 $j$번 장군에게 소속되지 않을 때라는 것을 명심하자. 일단 각 병사는 최대 $2$만큼의 유량을 보낼 수 있으므로 최소 한 명의 장군에게는 소속될 것이다. 또 각 장군은 최대 $N-K$만큼의 유량을 보낼 수 있으므로, 각 장군에게 소속되지 않은 병사는 최대 $N-K$명이다. 즉, 최소 $K$명은 소속된다는 것이다. 또한, 저 그래프의 최대 유량은 $2N \le 3(N-K)$이므로 $2N$이다. 따라서 각 병사가 무조건 $2$의 유량씩을 보내야 최대 유량이 되고, 각 병사는 정확히 한 명의 장군에게만 소속되게 된다.

 

이제 모델링을 완료했으니, 간선에 비용을 부여하면 된다. 이 경우 비용은 가운데 간선에만 매겨질 것이고, 각 비용은 자명하게도 $A_i$, $B_i$, $C_i$이다. 여기서 최소 비용 합을 고른 뒤, 전체 $A_i + B_i + C_i$에서 빼면 그것이 답, 즉 병사 능력치 합의 최댓값이 될 것이다.

 

다음으로 가능한 증가 경로의 종류를 보자.

 

 

첫 번째 종류는 위와 같이 단순히 병사 $i$와 장군 $j$의 커넥션을 만들어 주는 것이다. 즉, 병사 $i$가 장군 $j$에게 연결되지 않는다는 관계를 하나 형성해 주는 것이다.

 

 

두 번째 종류는 위와 같이 이미 형성된 커넥션 하나를 깨고, 두 개의 커넥션으로 바꾸는 것이다. 즉, 이미 존재하는 쌍 $(i, C)$를 없애고, 새로운 두 개의 쌍 $(i, D)$와 $(j, C)$로 바꾸는 것이다.

 

 

세 번째 종류는 위와 같이 이미 형성된 커넥션 두 개를 깨고, 세 개의 커넥션으로 바꾸는 것이다. 즉, 이미 존재하는 쌍 $(i, C)$와 $(j, D)$를 없애고, 새로운 세 개의 쌍 $(i, D)$, $(j, E)$, $(k, C)$로 바꾸는 것이다.

 

이제 이 세 가지 연산을 그리디하게 값싼 것부터 처리해 주면 MCMF 알고리즘의 원리(접근법 2)로 문제를 해결할 수 있을 것이다. 이것을 어떻게 처리해 주어야 할까?

 

세 가지 연산을 독립적으로 담당하는 자료구조를 만들어 주면 좋다. 위에서부터 차례로 $1$번, $2$번, $3$번 연산이라고 하자.

 

$1$번 연산을 처리하는 것은 쉽다. priority_queue 같은 걸 하나 관리하고 있으면 된다. $2$번이나 $3$번에서 끊기거나 생기는 관계들을 적당히 넣거나 빼 줘야 한다. 좌측이나 우측 간선의 용량이 더 이상 부족한 경우에는 무슨 짓을 해도 해당 간선에 새로 용량이 생기게 할 수 없으므로, 그냥 pq에서 영구히 제거해 줘도 된다.

 

$2$번 연산을 처리하는 것을 보자. WLOG, 현재 $(i, A)$ 쌍이 있는데, 이를 $(i, B)$와 $(j, A)$로 바꾸는 연산이 필요하다고 하자. 이때 $A$와 $B$를 고정한다면, 수많은 $(i, j)$ 쌍 중에서 어떤 것을 고르는 게 최적일까? 먼저 $i$를 고르자면, 일단 $(i, A)$ 쌍은 있지만 $(i, B)$ 쌍은 없다는 조건이 필요하고, 그러한 $i$ 중 $B_i - A_i$가 가장 작은 것이 좋아 보인다. 다음으로 $j$를 고르자면, 아직 소스로부터 유량을 $2$개 이상 받지 않은 것 중 $A_j$가 가장 작은 것을 고르면 될 것이다. 이런 식으로 $B_i - A_i$와 비슷한 형태의 6가지 식에 대해 각각 priority_queue를 관리하고, $A_j$에 대해서는 $1$번 연산의 pq를 사용하면 될 것이다.

 

$3$번 연산은 $2$번 연산에서 봐야 하는 pq의 개수가 늘어난 꼴이므로 딱히 추가로 신경써줄 것은 없다. 그러나 시작점/끝점 조건 때문에 priority_queue의 전체 개수가 $18$개로 늘어나게 된다. 그래도 어떻게 240ms밖에 안 걸리긴 한다. 시간 복잡도는 $O(18 N \log N)$이다.

BOJ 19654. Sequence

이 문제는 앞의 문제들보다 네트워크 플로우 모델링을 만드는 것이 더 까다롭다. 일단 각 $a_i$와 $b_i$를 선택하는 옵션을 나타내는 정점이 필요할 것이다. 그런데 $a_i$와 $b_i$를 함께 선택하는 $i$가 최소한 $L$개는 있어야 한다. 그렇다면, $a_i$와 $b_i$의 번호를 다르게 선택하는 것은 최대 $K-L$개로 제한될 것이다. 이 점을 생각해 다음과 같은 모델을 만들 수 있다.

 

 

빨간색은 간선의 용량이며, 따로 용량이 명시되지 않은 모든 간선의 용량은 $1$로 생각한다. 또한, 파란색은 간선의 비용이며, 따로 명시되지 않은 경우 비용이 $0$이라고 생각한다.

 

문제는 여기에서 $K$의 유량을 최대 비용으로 보내는 방법을 찾는 것이고, $a_i$들과 $b_i$들의 부호를 모두 바꾸면 최소 비용 문제로 바꾸어 생각할 수 있다.

 

이제 남은 일은 가장 이득이 큰 증가 경로를 찾는 일이다. 이 문제에서 가능한 형태는 다음 형태밖에 없음을 알 수 있다. 더 많은 형태가 존재하지만, 얻는 이득이 동일할 경우 $p \rightarrow q$ 간선에 흐르는 유량을 불필요하게 늘리지 않는 증가 경로를 선택한다고 생각하면 아래 경우로 한정할 수 있다.

• $S \rightarrow a_i \rightarrow b_i \rightarrow e$
• $S \rightarrow a_i \rightarrow p \rightarrow q \rightarrow b_j \rightarrow E$
• $S \rightarrow a_i \rightarrow b_i \rightarrow q \rightarrow b_j \rightarrow E$
• $S \rightarrow a_i \rightarrow p \rightarrow a_j \rightarrow b_j \rightarrow E$

그런데 이들 각각의 선택은 다음과 같이 말로 나타낼 수 있다.

• $(a_i, b_i)$ 쌍을 선택한다.
• 만약 $p \rightarrow q$ 간선에 유량이 남으면, $(a_i, b_j)$ 쌍을 선택한다.
• 이미 선택된 $a_i$에 대해 $b_i$를 추가해 주고, 새로운 $b_j$를 추가한다.
• 이미 선택된 $b_i$에 대해 $a_i$를 추가해 주고, 새로운 $b_j$를 추가한다.

위 네 가지 중 최선의 선택을 반복하는 그리디 알고리즘을 구현하면 문제를 풀 수 있다. priority_queue 여러 개를 관리하는 쪽이 가장 쉬운 구현인 것 같다. 시간 복잡도는 $O(N \log N)$이다.