免费10g网站空间站长工具网站
问题描述
给定一个图网络 G = ( V , E ) G=(V, E) G=(V,E)，网络中连边的权重代表最大容量，在这个图中找出从起点到终点流量最大的路径。
数学建模
集合：
I I I：点的集合；
E E E：边的集合。
常量：
d e d_e de：边 e e e上的最大容量；
变量：
x e x_e xe： e e e这条边的流量；
f f f：最大流量。
数学模型：
m a x f s . t . ∑ e ∈ o u t ( i ) x e − ∑ e ∈ i n ( i ) x e = { f , i = s − f , i = t 0 , e l s e 0 ≤ x e ≤ d e ， ∀ e ∈ E max f \\ s.t. \sum_{e\in out(i)}x_e - \sum_{e\in in(i)}x_e = \begin{cases} f, i=s\\ -f, i=t\\ 0, else \end{cases} \\ 0 \leq x_e \leq d_e，\forall e \in E maxfs.t.e∈out(i)∑xe−e∈in(i)∑xe=⎩ ⎨ ⎧f,i=s−f,i=t0,else0≤xe≤de，∀e∈E
问题求解
方式一：扔给求解器；
方式二：Ford-fulkerson（FFA）算法