最小割模型的应用VIP专享VIP免费

网络流网络流————最小割模型的应用最小割模型的应用[[一一]]引例引例[[二二]]基本概念基本概念[[三三]]三个重要问三个重要问题题[[四四]]经典例题欣经典例题欣赏赏2024年12月10日2[[一一]]引例：运输方案引例：运输方案『『UVA1069UVA1069』』如图为连接产品产地如图为连接产品产地VV11和销地和销地VV66的交通网，每一条边的交通网，每一条边（（VVii，，VVjj）表示从）表示从VVii到到VVjj的运输线，产品经这条边由的运输线，产品经这条边由VVii输输送到送到VVjj，边上的数字表示这条运输线的最大通行能力（简，边上的数字表示这条运输线的最大通行能力（简称容量）。产品经过交通网从称容量）。产品经过交通网从VV11输送到输送到VV66，现要求制定一，现要求制定一个输送方案，使得从个输送方案，使得从VV11运到运到VV66的产品数量最多。的产品数量最多。2024年12月10日311223344554444884422产地产地66销地销地11227733如图为一个可行的输送方案，边上的数字表示该运输线的实际运输量如图为一个可行的输送方案，边上的数字表示该运输线的实际运输量（单位：吨）。（单位：吨）。该运输方案表示：该运输方案表示：22吨产品沿有向路吨产品沿有向路PP11（（VV11，，VV22，，VV44，，VV66）运到销地；）运到销地；11吨产品沿有向路吨产品沿有向路PP22（（VV11，，VV22，，VV55，，VV66）运到销地；）运到销地；22吨产品沿有向路吨产品沿有向路PP33（（VV11，，VV33，，VV55，，VV66）运到销地。）运到销地。总共有总共有55吨产品从吨产品从VV11运到运到VV66。。2024年12月10日4[[一一]]引例：运输方案引例：运输方案『『UVA1069UVA1069』』11223344554444884422产地产地66销地销地11227733222222110022221100001122『『算法分析与设计算法分析与设计』』可行的运输方案必须满足以下三个条件：可行的运输方案必须满足以下三个条件：（（11）实际运输量不能是负的；）实际运输量不能是负的；（（22）每条边的实际运输量不能大于该边的容量；）每条边的实际运输量不能大于该边的容量；（（33）除了起点）除了起点VV11和终点和终点VV66，对其他顶点（中间点）来说，不能囤，对其他顶点（中间点）来说，不能囤积物资，即运到它那儿的物资是多少，从它那儿运走的物资也应该是多少。积物资，即运到它那儿的物资是多少，从它那儿运走的物资也应该是多少。思考思考：如何改进运输方案？即根据这个运输网，是否可增大运输量？：如何改进运输方案？即根据这个运输网，是否可增大运输量？2024年12月10日5[[一一]]引例：运输方案引例：运输方案『『UVA1069UVA1069』』我们找到一条有向路我们找到一条有向路PP44（（VV11，，VV22，，VV33，，VV44，，VV66）可）可再增加再增加11吨物资运输量，改进的方案如图所示：吨物资运输量，改进的方案如图所示：2024年12月10日6[[一一]]引例：运输方案引例：运输方案『『UVA1069UVA1069』』11223344554444884422产地产地66销地销地112277334422221111223333001111223344554444884422产地产地66销地销地1122773333222211002222330000观察有向路观察有向路PP66（（VV11，，VV33，，VV22，，VV44，，VV66）中，将正方）中，将正方向的边（向的边（VV11，，VV33）、（）、（VV22，，VV44）、（）、（VV44，，VV66）都可增加）都可增加运输量，而反方向的边（运输量，而反方向的边（VV33，，VV22）的运输量为）的运输量为11，现将反，现将反向边（向边（VV33，，VV22）的运量调到正向边（）的运量调到正向边（VV22，，VV44）上去完成，）上去完成，这样有向路这样有向路PP66（（VV11，，VV33，，VV22，，VV44，，VV66）的运量可增加）的运量可增加11。。2024年12月10日7[[一一]]引例：运输方案引例：运输方案『『UVA1069UVA1069』』11223344554444884422产地产地66销地销地1122773344332211222244330011至此，再找不到可“改进”的有向路了，所以，该交至此，再找不到可“改进”的有向路了，所以，该交通网的最大运输量为通网的最大运输量为88吨。吨。2024年12月10日8[[一一]]引例：运输方案引例：运输方案『『UVA1069UVA1069』』11223344554444884422产地产地6...