1、网络流满足容量约束，但一般不满足流量守恒约束。

A、对
B、错

参考答案：请扫码使用小程序查看答案

2、设G = <V1, V2, E>为二分图, |V1|≤|V2|, M为G中一个最大匹配, 且|M| = |V1|, 则称M为G的完备匹配，也是最大匹配。

A、对
B、错

参考答案：请扫码使用小程序查看答案

3、存在割 (A, B)使流值 v(f) = 割的容量cap(A, B).，则割 (A, B)是最小割。

A、对
B、错

参考答案：请扫码使用小程序查看答案

4、给定连通图G, BFS遍历得到层次图，如果同一层中的结点无边相连，则G是二分图。

A、对
B、错

参考答案：请扫码使用小程序查看答案

5、有下界的流通问题不一定有可行流。

A、对
B、错

参考答案：请扫码使用小程序查看答案

6、Dinic算法的时间复杂度为（）

A、mn2
B、mn
C、m2n
D、m2logC

参考答案：请扫码使用小程序查看答案

7、如果每条边的最大容量为1，则时间复杂度是O（nm）的网络流算法有

A、FF算法
B、容量缩放算法
C、EK算法
D、Dinic算法

参考答案：请扫码使用小程序查看答案

8、给定二分图G = <V, E>中无孤立点，|V|=n，其最大流算法求得最大流f, 则G的（）=n-f

A、最大独立数
B、最大匹配数
C、最小顶点覆盖
D、最小边覆盖

参考答案：请扫码使用小程序查看答案

9、改进FF网络流算法，可以通过选择（）增广路，降低时间复杂度。

A、最大容量
B、最短路径
C、最大瓶颈容量
D、边数最少

参考答案：请扫码使用小程序查看答案

10、带需求的流通必须满足供给和 = 需求和

A、对
B、错

参考答案：请扫码使用小程序查看答案

当前位置：首页 ＞课程 ＞算法分析与设计

1、网络流满足容量约束，但一般不满足流量守恒约束。

2、设G = <V1, V2, E>为二分图, |V1|≤|V2|, M为G中一个最大匹配, 且|M| = |V1|, 则称M为G的完备匹配，也是最大匹配。

3、存在割 (A, B)使流值 v(f) = 割的容量cap(A, B).，则割 (A, B)是最小割。

4、给定连通图G, BFS遍历得到层次图，如果同一层中的结点无边相连，则G是二分图。

5、有下界的流通问题不一定有可行流。

6、Dinic算法的时间复杂度为（）

7、如果每条边的最大容量为1，则时间复杂度是O（nm）的网络流算法有

8、给定二分图G = <V, E>中无孤立点，|V|=n，其最大流算法求得最大流f, 则G的（）=n-f

9、改进FF网络流算法，可以通过选择（）增广路，降低时间复杂度。

10、带需求的流通必须满足供给和 = 需求和

算法分析与设计

当前位置：首页 ＞课程 ＞算法分析与设计

1、网络流满足容量约束，但一般不满足流量守恒约束。

2、设G = <V1, V2, E>为二分图, |V1|≤|V2|, M为G中一个最大匹配, 且|M| = |V1|, 则称M为G的完备匹配，也是最大匹配。

3、存在割 (A, B)使流值 v(f) = 割的容量cap(A, B).，则割 (A, B)是最小割。

4、给定连通图G, BFS遍历得到层次图，如果同一层中的结点无边相连，则G是二分图。

5、有下界的流通问题不一定有可行流。

6、Dinic算法的时间复杂度为（）

7、如果每条边的最大容量为1，则时间复杂度是O（nm）的网络流算法有

8、给定二分图G = <V, E>中无孤立点，|V|=n，其最大流算法求得最大流f, 则G的（）=n-f

9、改进FF网络流算法，可以通过选择（）增广路，降低时间复杂度。

10、带需求的流通必须满足供给和 = 需求和

算法分析与设计

当前位置：首页＞课程＞算法分析与设计