# Dynamic Flow

Dynamic Flow는 간선 용량, 비용, 활성 상태, 시간 단계가 바뀌는 상황에서 flow 값을 매번 처음부터 계산하지 않도록 모델링하는 주제입니다. 완전한 online dynamic max flow는 매우 어렵지만, 대회에서는 residual graph 재사용, 시간 확장 네트워크, batch rebuild, offline interval 처리처럼 제한된 형태로 자주 나타납니다.

## 문제 신호

| 문제 표현 | Dynamic Flow 관점 |
| --- | --- |
| 간선 용량이 계속 증가한다 | residual graph에서 추가 augment |
| 간선이 삭제되거나 용량이 줄어든다 | 기존 flow를 되돌리거나 rebuild 필요 |
| 시간마다 이동 가능 간선이 다르다 | time-expanded network |
| 같은 네트워크에 source/sink query가 많다 | cut reuse 또는 batch rebuild |
| flow 값이 임계값 이상인지 반복해서 묻는다 | parametric feasibility |

flow는 단순 connectivity보다 상태가 무겁습니다. 간선 하나가 바뀌어도 모든 flow conservation 제약이 영향을 받을 수 있으므로, update 종류를 좁히지 않으면 안정적인 구현을 만들기 어렵습니다.

## Static Flow와 무엇이 다른가

정적 max flow는 residual graph에서 augmenting path를 더 이상 찾을 수 없으면 끝납니다. Dynamic Flow에서는 이미 구한 residual graph가 다음 query의 출발점이 됩니다.

```text
old network + old flow
update edge capacity
repair feasibility if needed
augment or rebuild
```

capacity 증가와 source/sink가 그대로인 경우에는 기존 flow가 여전히 feasible합니다. 그래서 추가로 열린 residual capacity만 이용해 더 augment하면 됩니다. 반대로 capacity 감소나 edge deletion은 기존 flow가 그 edge를 쓰고 있었을 수 있어 feasibility repair가 먼저 필요합니다.

## Update 종류별 난이도

| update | 기존 flow feasible? | 실전 접근 |
| --- | --- | --- |
| capacity increase | 유지됨 | residual에서 추가 augment |
| new edge insert | 유지됨 | 새 residual edge 추가 후 augment |
| capacity decrease | 깨질 수 있음 | 사용 flow 초과분을 되돌리거나 rebuild |
| edge delete | 깨질 수 있음 | tree/cut 관점보다 rebuild가 안전 |
| source/sink change | 대부분 재사용 어려움 | query batch나 Gomory-Hu류 검토 |

문제가 capacity 증가만 허용하는지, deletion이 섞이는지를 먼저 봅니다. 이 한 줄 조건이 풀이 난도를 크게 바꿉니다.

## Time-Expanded Network

시간 단계가 작거나 이동 시간이 명시되면 update를 직접 처리하지 않고 정적인 큰 네트워크로 바꿀 수 있습니다.

```text
node(time, vertex)
wait edge: node(t, v) -> node(t+1, v)
move edge: node(t, u) -> node(t+1, v)
```

이 모델은 "시간 t에 어떤 간선이 활성인지"를 정적 edge 집합으로 펼칩니다. 최단 시간 evacuation, 시간표가 있는 이동, 라운드별 capacity 제한 문제에서 특히 자연스럽습니다.

## Time Expansion 구현 조각

아래 코드는 시간 구간 `[start, end)` 동안 활성인 directed edge를 시간 확장 네트워크의 간선 목록으로 바꿉니다.

totalSupply는 비음수이며 기다림을 허용할 때의 충분한 용량 상한입니다. 각 arc capacity와 정점 번호는 유효해야 하고 (timeCount+1)*vertexCount가 int 범위여야 합니다. 실제 저장은 T+1층이며 이동·기다림은 한 시간 단위입니다.

> **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

```cpp compile-check
#include <algorithm>
#include <vector>
using namespace std;

struct DynamicArc {
    int from = 0;
    int to = 0;
    int start = 0;
    int end = 0;
    int capacity = 0;
};

struct ExpandedArc {
    int from = 0;
    int to = 0;
    int capacity = 0;
};

int timedNode(int time, int vertex, int vertexCount) {
    return time * vertexCount + vertex;
}

vector<ExpandedArc> buildTimeExpandedNetwork(
    int vertexCount,
    int timeCount,
    const vector<DynamicArc>& arcs,
    int totalSupply
) {
    vector<ExpandedArc> result;

    for (int t = 0; t < timeCount; ++t) {
        for (int v = 0; v < vertexCount; ++v) {
            result.push_back({
                timedNode(t, v, vertexCount),
                timedNode(t + 1, v, vertexCount),
                totalSupply
            });
        }
    }

    for (const DynamicArc& arc : arcs) {
        int left = max(0, arc.start);
        int right = min(timeCount, arc.end);
        for (int t = left; t < right; ++t) {
            result.push_back({
                timedNode(t, arc.from, vertexCount),
                timedNode(t + 1, arc.to, vertexCount),
                arc.capacity
            });
        }
    }

    return result;
}
```

이 함수는 max flow 구현 자체가 아니라 모델 변환부입니다. 변환 뒤에는 일반 Dinic이나 Min-Cost Flow를 그대로 붙이면 됩니다.

## 작은 예시

```text
정점: S, A, T
시간: 0..2
활성 간선:
  t=0: S -> A capacity 2
  t=1: A -> T capacity 1
```

time-expanded network에서는 `S0 -> A1 -> T2` 경로가 됩니다. 같은 사람이나 물건이 한 단계 쉬어도 되면 wait edge가 필요합니다. wait edge를 빼면 "반드시 매 시간 이동"하는 다른 문제가 됩니다.

## 어떤 접근을 고를까

| 조건 | 우선 접근 |
| --- | --- |
| capacity 증가만 있음 | residual graph 재사용 |
| deletion이 적고 query block이 큼 | block rebuild |
| 모든 update를 미리 앎 | interval over time + offline 처리 |
| 시간 단계가 작음 | time-expanded network |
| 비용이 convex하게 증가 | convex cost flow 또는 edge split |

flow update 자체보다 문제 제약을 정적 모델로 바꾸는 편이 구현 위험이 낮습니다. 특히 삭제가 섞이면 완전 동적 구조를 바로 시도하지 말고 rebuild 기준 구현부터 만듭니다.

## Cut 관점

max flow 값은 min cut capacity와 같습니다. update가 cut capacity를 어떻게 바꾸는지 보면 불필요한 재계산을 줄일 수 있습니다.

```text
capacity increase on non-critical edge -> answer may stay same
capacity increase crossing every min cut -> answer may increase
capacity decrease on used critical edge -> answer may decrease
```

하지만 "critical edge인지"를 유지하는 것도 쉽지 않습니다. 이 관점은 proof와 pruning에는 좋지만, 구현은 residual augment나 rebuild로 시작하는 편이 안전합니다.

## 로컬 완결형 연습

### Residual Reuse Trace

정점 `S, A, B, T`와 아래 간선이 있는 작은 네트워크를 잡습니다.

```text
S -> A capacity 2
S -> B capacity 2
A -> T capacity 1
B -> T capacity 2
A -> B capacity 1
```

초기 max flow는 3입니다.

```text
S -> A -> T : 1
S -> B -> T : 2
```

이 상태에서 `A -> T` capacity를 1 늘리면 old flow는 여전히 feasible입니다. residual graph에는 `S -> A -> T`로 1을 더 보낼 수 있으므로 답은 4가 됩니다.

반대로 `S -> B` capacity를 1 줄이면 old flow 2가 capacity 1을 초과합니다. 이때는 추가 augment만으로는 고칠 수 없고, 초과 flow를 되돌리거나 rebuild해야 합니다.

이 trace에서 써야 할 표는 아래 네 칸입니다.

| 단계 | max flow | 바뀐 간선 | 가능한 처리 |
| --- | ---: | --- | --- |
| 초기 | 3 | 없음 | Dinic 한 번 |
| capacity 증가 | 4 | `A -> T += 1` | residual에서 추가 augment |
| capacity 감소 | 3 (재계산) | `S -> B -= 1` | repair 또는 rebuild |
| source/sink 변경 | 알 수 없음 | `S/T` 변경 | batch query나 rebuild |

핵심은 "capacity 증가에서는 기존 flow가 계속 feasible하다"는 조건입니다. 이 조건을 놓치면 dynamic flow를 dynamic connectivity처럼 단순 rollback으로 착각하게 됩니다.

### Incremental Max Flow Runner

아래 로컬 문제는 실제 Dinic 구현까지 붙여서 끝낼 수 있는 형태입니다.

#### 입력

초기 directed network와 `Q`개의 capacity increase query가 주어집니다. 각 query 뒤의 max flow 값을 출력합니다.

```text
N M Q S T
u1 v1 c1
...
uM vM cM
edgeId1 delta1
...
edgeIdQ deltaQ
```

간선 ID는 입력 간선의 0-based index입니다. `delta`는 양수입니다.

#### 제한

- `2 <= N <= 300`
- `1 <= M <= 2000`
- `0 <= Q <= 2000`
- `0 <= S, T < N`, `S != T`
- 모든 capacity와 delta는 `1..10^6`

#### 예시

```text
4 5 2 0 3
0 1 2
0 2 2
1 3 1
2 3 2
1 2 1
2 1
0 1
```

초기 flow는 3입니다. 첫 query는 `1 -> 3` capacity를 1 늘려 flow가 4가 됩니다. 두 번째 query는 `0 -> 1` capacity를 늘리지만 `T`로 들어가는 병목이 이미 찼으므로 답은 그대로 4입니다.

```text
4
4
```

#### 구현 기준

1. 초기 간선마다 Dinic edge index를 저장한다.
2. 초기 max flow를 한 번 계산한다.
3. query가 들어오면 해당 forward edge의 residual capacity를 `delta`만큼 늘린다.
4. 같은 residual graph에서 Dinic을 다시 호출해 추가 flow만 더한다.
5. 누적 flow를 출력한다.

Dinic을 다시 호출해도 reverse edge와 기존 residual capacity를 초기화하면 안 됩니다. 이 연습의 목적은 "정적 max-flow 구현을 재사용하되 residual state를 유지하는 법"을 확인하는 것입니다.

#### Stress 검증

작은 입력에서는 query마다 원래 capacity 배열을 갱신한 뒤 Dinic을 처음부터 돌리는 baseline과 비교합니다.

```text
for seed in 1..1000:
    random graph and positive increase queries
    answer_incremental = residual reuse
    answer_rebuild = rebuild Dinic every query
    assert answer_incremental == answer_rebuild
```

capacity decrease query를 일부러 섞으면 이 assert가 깨질 수 있어야 합니다. 그 반례가 바로 이 기법의 적용 경계입니다.