运输问题4

Grade 0 Open Time Wednesday, 16 January 2013, 9:40 am
Discount 0.8 Time Discount Wednesday, 16 January 2013, 9:40 am
Allow late Yes Close Time Wednesday, 16 January 2013, 9:40 am
Input file maxflowd.in Output file maxflowd.out
【问题描述】
    一个工厂每天生产若干商品,需运输到销售部门进行销售。从产地到销地要经过某些城镇,有不同的路线可以行走,每条两城镇间的公路都有一定的流量限制。公路设有收费站,每通过一辆车,要交纳过路费。请你计算,在不考虑其它车辆使用公路的前提下,如何使产地运输到销地的商品最多,并使费用最少。
【输入格式】
输入文件有若干行
第一行,一个整数n,表示共有n个城市(2<=n<=100),产地是1号城市,销地是n号城市
第二行,一个整数,表示起点城市
第三行,一个整数,表示终点城市
下面有n行,每行有2*n个数字。第p行第2*q-1,2*q列的数字表示城镇p与城镇q之间有无公路连接。数字为0表示无,大于0表示有公路,且这两个数字分别表示该公路流量和每车费用。
【输出格式】
输出文件有一行
第一行,1个整数n,表示最小费用为n。
【输入输出样例】
输入文件名: maxflowd.in
6
1
6
0 0 1 3 5 10 0 0 0 0 0 0
0 0 0 0 0 0 5 7 0 0 0 0
0 0 0 0 0 0 0 0 2 8 0 0
0 0 0 0 1 3 0 0 0 0 3 5
0 0 2 4 0 0 0 0 0 0 2 6
0 0 0 0 0 0 0 0 0 0 0 0
输出文件名:maxflowd.out
63