编程介的小学生 2019-01-13 14:27 采纳率: 0.2%
浏览 385
已采纳

最小费用流的问题,数据结构讨论下怎么实现最小费用的算法,采用C编程的办法

Problem Description
在地球上的一个鲜为人知的角落,住着这样一群人.他们整日与算法为伴,以研究出高效的算法为荣.就连竞选村长都是以Word Final的标准进行的.这里的算法风气之浓厚,就连当地的动物们都受到了极大的影响.旺财是村长--TCL(相当于世界冠军的水平)的爱犬,从小就受到村长一家的熏陶,当别的小动物都还在算A+B的的时候,旺财已经学会"迪杰斯特拉"和"贝尔曼-佛德"了,因此他一直是当地的小动物们崇拜的对象,它们眼中的最有希望进Animal Kingdom World Final的明日之星,就连村里面耕地的老牛们见了他都要叫声"大牛好~".
可是,旺财也有他的苦衷.TCL对待他实在是太好了,每天都请医疗专家周海角为旺财开出许多的保健药品(据说TCL那么牛就是因为从小吃周海角开的药).周海角作为一名医疗专家,有着数十年的江湖行医经验,他的药方不是一般人能开得出来的.他每次都会开出两张药方,第一张药方上写有N1种药品(每种药的编号分别为1,2,3……,N1),第二张药方上写有N2种药品(编号分别为N1+1,N1+2,N1+3……,N1+N2),之所以要这样,是因为第一张药方上的药只有村北的药店里才有,而第二张药方上的药只有村南的药店里才有,并且,药方上还明确指出哪些药必须在哪些药服用之后才能服用,否则会有脑残的危险!还需要一提的药是不能打包带回去,只能在相应的药店里在专家指导下当场服用,安全第一嘛。旺财还面临的一个问题是:村北和村南的药店相隔甚远,而且两地之间还有一个规定凡是4条腿或4个轮子的东西经过都要交钱的收费站,作为一条精通算法的小狗,旺财始终把"提高效率减小耗费"作为自己的座右铭.他在想要怎样吃药才能使跑远路的次数最少,这样过路费也会最小.从村南到村北或从村北到村南算一次跑远路,到最后吃完药跑回家,也算一次哦.

Input
有多组输入数据.每组数组的第一行有三个整数N1, N2, M. 接下来有M行数组,每行有两个整数 a, b, 分别表示在吃第a种药之前,需要先吃第b种药. 最后一组数据后,会有三个0表示输入结束。所有的数据中, 1<=N1,N2<=60000, 0<=M<=120000, 1<=a,b<=N1+N2.

Output
每组数据输出一个整数,表示旺财把药房上的药吃完所需的跑远路的次数.

Sample Input
5 3 3
1 2
5 1
3 2
0 0 0

Sample Output
3

  • 写回答

1条回答 默认 最新

  • threenewbee 2019-12-31 02:05
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥150 IED中开关量采样信号通道、以及程序流程的设计
  • ¥15 改动头文件造成的编译错误如何解决
  • ¥20 woocommerce 注册按键重定向
  • ¥100 求书法图像文字切割代码
  • ¥15 同一个波形探测距离不同的目标,为什么fft之后得到的频谱图会发生移动,不应该时移不改变幅度谱吗(标签-matlab)(相关搜索:matlab仿真)
  • ¥20 【初学者】comsol周期性电流如何设置?例如通电三天断电三天
  • ¥15 Proteus仿真程序只能执行一次
  • ¥15 语音识别websocket报错
  • ¥15 激光器,引脚问题,无法处理
  • ¥20 求写一份!只提交Mapper映射文件 如:UsersMapper.xml