首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 其他教程 > 其他相关 >

最小用费最大流算法

2013-01-26 
最小费用最大流算法反复寻找费用最小路径,然后在该路径上使流量增大;寻找最小费用路径时,不考虑剩余容量为

最小费用最大流算法

反复寻找费用最小路径,然后在该路径上使流量增大;寻找最小费用路径时,不考虑剩余容量为 0 的边;虽然网络流图是有向图,但是为了寻找包含反向边的路径,对每条正向边都有可能生成出反向边(当正向边上有流量时,就有容量等于流量的反向边);

NetworkFlowGraph.h 类头文件:

//============================================================================// Name        : MinCostFlow.cpp// Author      : Qichi// Version     :// Copyright   : Copyright QiChi// Description : Hello World in C++, Ansi-style//============================================================================#include <iostream>#include "NetworkFlowGraph.h"using namespace std;int main() {double flow, cost;NetworkFlowGraph *inst = new NetworkFlowGraph(5,0,4);inst->insert(0,1,10,4);inst->insert(0,2,8,1);inst->insert(2,1,5,2);inst->insert(2,3,10,3);inst->insert(1,3,2,6);inst->insert(1,4,7,1);inst->insert(3,4,4,2);inst->min_cost_max_flow(flow, cost);cout << flow << ":" << cost << endl;delete inst;return 0;}


热点排行