---
tags: 圖論
title: 網路流初步
---
:::info
- #### 題敘很臭很長的模板題 [TIOJ 2117](https://tioj.ck.tp.edu.tw/problems/2117)
:::

:::success
# 網路流 Flow

## 名詞解釋

- Source(s)：源點
- Sink(t)：匯點
- Capacity\(c\)：容量
- Flow(f)：流量
- Node：節點
- Arc：弧（邊）
- Cost：費用

## 定義

- 在每條邊都有容量的有向圖分配流
- 有且僅有一個源點，入度為0；有且僅有一個匯點，出度為0

## 性質
- 容量限制：$f(u, v) \le c(u, v)$
- 斜對稱性：$f(u, v)=-f(v, u)$
- 流量守恆：$\sum_{(u, v)\in E}f(u, v)=0$
:::

:::success
# 最大流問題

*（數字表capacity）*

## 定義

- 求S到T的最大流量$MAX(|f|=\sum_{(s, v)\in E}f(s, v)=\sum_{(u, t)\in E}f(u, t))$

## Edmonds-Karp演算法

### 殘量網路

- 計算每條弧上容量與流量差，形成殘量網路
- $c'(u, v)=c(u, v)-f(u, v)+f(v, u)$
- 殘量網路邊數最多可以達到原圖的兩倍

### 增廣路徑

- 殘量網路中由S通向T的有向道路
- 求出路徑中所有殘量的最小值$min(c'(u, v))=d$
- 將路徑中所有弧的流量增加$d$
- 重複直到殘量網路中不存在增廣路徑

## 實作

1. 建立殘量網路
2. 用BFS尋找增廣路徑
3. 增加每條增廣路徑的流量
4. 重複直到不存在增廣路徑
:::

:::success
# 最大流最小費用問題

## 定義

- 給予每條弧單位流量所需的費用$c$
- 在流量最大化$|f|=MAX(\sum_{(s, v)\in E}f(s,v )=\sum_{(u, t)\in E}f(u, t))$的前提下最小化總費用

## 實作

- 網路流圖最大流量為一定值，無論如何增大流量，最後都會達到唯一最大流量
- Greedy想法：每次在DFS同時記錄增廣路徑單位流量所需的總費用，選擇目前費用最小的增廣路徑增加流量，直到達到最大流量，則此時累計費用即為最大流量最小費用
:::

:::success
# 最大流最小割

## 定義

## 證明

:::