67-算法设计

7.10.2　算法设计

（1）构建网络

根据输入的数据，按顺序对景点编号，即景点 i对应结点i，对每个结点拆点，拆为两个结点i和i'，且从i到i'连接一条边，边的容量为1，单位流量费用为0；源点和终点拆点时，边的容量为2，单位流量费用为0；如果景点i到景点j可以直达，则从结点i'到结点j连接一条边，边的容量为1，单位流量费用为−1，创建混合网络。

（2）求网络最小费用最大流

（3）输出最优的旅游路线

从源点出发，沿着flow>0且cost0的方向深度优先遍历，到达终点后，再沿着flow<0且cost0的方向深度优先遍历，返回到源点。

输出：首先是出发景点名，然后按遍历顺序输出其他景点名，最后回到出发景点。如果问题无解，则输出“No Solution!”。